DSA · Chapter 19 of 40
Trees
A tree is a hierarchical structure of nodes with one root and no cycles; each node has children and exactly one parent (except the root). A binary tree limits each node to at most two children.
Height is the longest path from root to leaf, and it determines the cost of most tree operations — a balanced tree has height O(log n) while a degenerate tree has height O(n).
Vocabulary
Root, leaf, parent, child, sibling, depth (distance from root), height (distance to deepest leaf), subtree.
Types
Full, complete and perfect binary trees describe how children are filled; balanced trees keep height near log n.
Example 1 (python)
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(root.left.val, root.right.val)Output
2 3A binary tree node holds a value plus left and right children.
Example 2 (python)
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
print(height(root))Output
2Height is computed recursively from the leaves upward.
Key points
- A tree has one root and no cycles.
- Binary trees have at most two children per node.
- Height drives operation cost.
- Balanced height is O(log n); worst case is O(n).
💡 Note: Most tree code is recursive with a None base case.