What is a tree data structure and how does it work?
A tree data structure is a hierarchical collection of connected nodes in which each node has one parent, except the root, and zero or more children. Trees model relationships such as file systems, organization charts, database indexes, and decision processes.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Concepts
A tree is normally rooted, meaning it has one top node called the root.
-
Node: Contains a value and references to its children.
-
Edge: A connection between a parent and a child.
-
Root: The node without a parent.
-
Leaf: A node without children.
-
Parent and child: Nodes directly connected in the hierarchy.
-
Depth: The number of edges from the root to a node; the root has depth
0. -
Height: The number of edges along the longest downward path to a leaf; a single-node tree has height
0. -
Subtree: Any node together with all of its descendants.
A general tree allows each node to have any number of children. A binary tree restricts every node to at most two children, conventionally named left and right.
Common Tree Variants
These terms describe different properties and should not be used interchangeably:
-
Binary tree: Each node has at most two children.
-
Binary search tree (BST): A binary tree with an ordering rule: values in a node’s left subtree are smaller, and values in its right subtree are larger. A duplicate-key policy must be defined separately.
-
Complete binary tree: Every level except possibly the last is full, and the last level is filled from left to right.
-
Full binary tree: Every node has either exactly zero or exactly two children.
-
Perfect binary tree: Every internal node has two children, and every leaf is at the same depth. It is both full and complete.
-
Balanced tree: A tree whose height remains O(log n). One common height-balancing invariant, used by AVL trees, requires the left and right subtree heights at every node to differ by at most one.
How Trees Are Represented
A binary tree is commonly represented through references:
-
leftpoints to the left child. -
rightpoints to the right child. -
In the Python 3.12 representation, both are
Nonewhen the child does not exist.
Other representations include parent pointers, adjacency lists, and array-based layouts such as heap indexing. The representation does not change the tree’s logical hierarchy.
Preorder, inorder, and postorder traversals can be implemented recursively or iteratively with an explicit stack. Level-order traversal uses breadth-first search with a queue, normally collections.deque in Python.
Unlike a list or queue, a tree does not define one universal traversal. The required order depends on the application: parent-before-child, children-before-parent, sorted order, or level-by-level processing.
Complexity
Let n be the number of nodes, h the tree height, and w the maximum number of nodes on one level.
| Operation | Best | Average | Worst | Auxiliary space |
|---|---|---|---|---|
| Access the root | O(1) | O(1) | O(1) | O(1) |
| Traverse all nodes | O(n) | O(n) | O(n) | O(h) for recursive DFS; O(w) for BFS |
| Search by value in an unordered binary tree | O(1) | O(n) | O(n) | O(1) iterative or O(h) recursive |
| Search in a BST | O(1) | O(log n) | O(n) | O(1) iterative or O(h) recursive |
| Insert into a BST | O(1) | O(log n) | O(n) | O(1) iterative or O(h) recursive |
Traversal is linear because every node is visited once. A BST operation follows one root-to-leaf path, taking O(h); it becomes O(n) when the tree is skewed. Average BST bounds assume a reasonably balanced tree or random insertion order.
Auxiliary space includes the recursion stack or queue but excludes the input tree itself. The stored tree occupies O(n) space. DFS uses O(h) stack space, while BFS uses O(w) queue space.
Example and Traversal Orders
Consider the tree A(B(D, E), C), where A is the root, B and C are its children, and D and E are leaves.
-
Preorder, root-left-right:
A, B, D, E, C -
Inorder, left-root-right:
D, B, E, A, C -
Postorder, left-right-root:
D, E, B, C, A -
Level order, breadth-first:
A, B, C, D, E
For a BST with distinct keys, inorder traversal produces values in sorted order. For an arbitrary binary tree, it simply visits the left subtree, the node, and then the right subtree.
Common Pitfalls and Interview Tips
-
Height convention: Height counts edges here, so an empty tree has height
-1and a one-node tree has height0. -
Edge cases: Define behavior for an empty tree and one-node tree. Negative values are valid; duplicates require a BST policy, and inserting already sorted values can create a skewed tree.
-
Recursion limits: Recursive traversal of a highly skewed tree can approach Python’s recursion limit of about 1000. Use an explicit stack when depth is not bounded.
-
Input mutation: Traversals should not change node links unless rebuilding the tree is intentional.
-
Trees versus graphs: A disconnected graph or a graph containing a cycle is not a valid tree. Use a visited set when processing general graph input.
-
Integer overflow: Python integers do not overflow, but node counts or indices may overflow in fixed-width languages.
-
BST assumptions: A BST search is not logarithmic unless the tree remains reasonably balanced.
-
Common follow-up: Interviewers often ask for iterative traversal, BST validation, lowest common ancestor, or maximum depth.