A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike arrays or linked lists, trees represent hierarchical relationships and enable efficient searching, insertion, and organization of data.
What Makes a Tree?
A tree has these properties:
One node is designated as the root
Every other node has exactly one parent
There are no cycles (no path leads back to itself)
All nodes are connected (there's a path from root to every node)
Essential Terminology
Term
Definition
Root
The topmost node with no parent
Parent
The node directly above a given node
Child
A node directly below a given node
Sibling
Nodes that share the same parent
Leaf
A node with no children
Internal Node
A node with at least one child (not a leaf)
Ancestor
Any node on the path from root to a given node
Descendant
Any node reachable by going down from a given node
Subtree
A node and all its descendants
Height vs Depth vs Level
These terms are often confused. Here's the distinction:
Term
Definition
Depth
Distance from root to node (root has depth 0)
Height
Distance from node to deepest leaf (leaves have height 0)
Level
Same as depth (sometimes 1-indexed)
Tree Height
Height of the root node
Types of Trees
Type
Definition
Binary Tree
Each node has at most 2 children (left and right)
N-ary Tree
Each node can have any number of children
Full Binary Tree
Every node has 0 or 2 children (never just 1)
Complete Binary Tree
All levels filled except last, which fills left to right
Perfect Binary Tree
All internal nodes have 2 children, all leaves at same level
Balanced Binary Tree
Height difference between subtrees is at most 1 for every node
Binary Search Tree
Left subtree values < node < right subtree values
Tree Properties & Formulas
Property
Formula
Edges in any tree
n - 1 (for n nodes)
Min height (balanced)
logâ‚‚(n)
Max height (skewed)
n - 1
Nodes in perfect tree
2^(h+1) - 1
Leaves in perfect tree
2^h
Max nodes at level k
2^k (for binary tree)
When to Use Trees
Hierarchical data: File systems, org charts, HTML DOM
Fast search: BST provides O(log n) lookup when balanced
Sorted data: BST maintains sorted order efficiently
Priority queues: Heaps (complete binary trees)
Prefix matching: Tries for string operations
Expression parsing: Abstract syntax trees
Common Interview Tips
Clarify the tree type: Is it binary? BST? Balanced? This affects your approach.
Ask about constraints: Can values be negative? Duplicates allowed? How large can the tree be?
Consider edge cases: Empty tree (null root), single node, skewed tree (like a linked list).
Know your terminology: Being precise about height vs depth shows mastery.
Think recursively: Trees are recursive structures - most solutions are naturally recursive.
aloalgo