General Tree A general tree is a hierarchical data structure where each node can have any number of children, unlike binary trees which are limited to two children. Trees are non-circular structures that organize data in parent-child relationships.
Tree vs Graph The key distinction between trees and graphs:
Trees are NOT circular - no cycles exist, creating a strict hierarchyGraphs CAN be circular - cycles are allowed between nodesNode Structure General tree nodes are more flexible than binary tree nodes:
class Node { int value ; Node parent = null ; public LinkedList < Node > children = new LinkedList < Node >(); public Node ( int value ) { this . value = value; } public Node ( int value , Node parent ) { this . value = value; this . parent = parent; } }
Key Components:
value : Data stored in the nodeparent : Pointer to the parent nodechildren : List of child nodes (can be any number)
Unlike binary trees with fixed left/right pointers, general trees use a list structure to accommodate variable numbers of children.
Core Operations
Adding Nodes to Tree Nodes are added by specifying a parent value and the new node’s value. public void addNode ( int parent, int value) { Node parentNode = findNode (parent); if (parentNode == null ) return ; // Parent must exist boolean exist = contains (value); if (exist) return ; // Values must be unique Node childNode = new Node (value, parentNode); nodes . add (childNode); parentNode . children . add (childNode); }
Time Complexity: O(n) - due to findNode and contains operationsSpace Complexity: O(1)
Searching for Nodes Helper function to locate nodes by value. private Node findNode ( int value) { for ( Node node : nodes) if ( node . value == value) return node; return null ; } private Boolean contains ( int value) { for ( Node node : nodes) if ( node . value == value) return true ; return false ; }
Time Complexity: O(n) - can be optimized to O(1) with HashMapSpace Complexity: O(1)Performance can be improved by maintaining a HashMap of values to nodes, reducing search time to O(1).
Retrieving Child Nodes Returns all children of a given parent node. public List < Integer > children ( int parent) { Node parentNode = findNode (parent); if (parentNode == null ) return null ; LinkedList < Integer > childrenList = new LinkedList < Integer >(); for ( Node child : parentNode . children ) childrenList . add ( child . value ); return childrenList; }
Time Complexity: O(n + c) where c is the number of childrenSpace Complexity: O(c) for the output list
Finding Parent Node Retrieves the parent of a given child node. public int parent ( int child) { Node childNode = findNode (child); if (childNode == null ) return - 1 ; // Error: node not found return childNode . parent . value ; }
Time Complexity: O(n) - due to findNodeSpace Complexity: O(1)
Tree Height Determines the maximum depth from root to any leaf. public int height () { int [] maxHeight = new int [ 1 ]; height (root, 1 , maxHeight); return maxHeight[ 0 ]; } private int height ( Node node, int currentHeight, int [] maxHeight) { if (node == null ) return currentHeight; for ( Node child : node . children ) { int childHeight = height (child, currentHeight + 1 , maxHeight); if (childHeight > maxHeight[ 0 ]) maxHeight[ 0 ] = childHeight; } return currentHeight; }
Time Complexity: O(n) - visits all nodesSpace Complexity: O(h) - recursion stack depth
Tree Visualization Recursively prints the tree structure showing node connections. public void print () { print (root); } private void print ( Node node) { if (node == null ) return ; String children = "[" ; for ( Node child : node . children ) children += child . value + ", " ; System . out . println ( node . value + " is connected to " + children + "]" ); for ( Node child : node . children ) print (child); }
Time Complexity: O(n)Space Complexity: O(h) - recursion depthTree Properties
Hierarchical Structure Trees represent hierarchical relationships with a clear parent-child structure starting from a single root.
No Cycles Trees are acyclic - there’s exactly one path between any two nodes, preventing circular references.
Variable Children Each node can have any number of children (0 to many), unlike binary trees’ two-child limit.
Unique Values Each value appears exactly once in the tree structure for efficient searching.
Use Cases General trees are ideal for representing:
File Systems : Directories and subdirectoriesOrganization Charts : Company hierarchiesXML/HTML DOM : Nested document structuresAI Decision Trees : Multi-branch decision makingFamily Trees : Genealogical relationshipsCategory Taxonomies : Product classifications
Optimization Strategy : Maintain a HashMap mapping values to nodes to reduce search operations from O(n) to O(1):private HashMap < Integer , Node > nodeMap = new HashMap <>();
This significantly improves performance for find, contains, and related operations. Interactive Visualizer
Explore General Trees Use the interactive visualizer to build and explore general tree structures
Binary Search Tree Learn about binary trees with two children per node
Tree Traversals Discover different methods to traverse tree structures