Trees
Terminology and Structure
The root is the topmost node of the tree. It is the starting point. There is exactly one root in any tree. It has no parent. In the company analogy, the CEO is the root.
A leaf node is a node that has no children. It is at the bottom of the tree. In the company analogy, employees who manage nobody are the leaves.
An internal node is any node that has at least one child. It is not a leaf. The root is also an internal node (unless the tree has only one node). All managers and VPs are internal nodes in our analogy.
Parent: The node directly above a given node is its parent. Every node except the root has exactly one parent.
Child: Nodes directly below a given node are its children. A node can have zero or more children.
Sibling: Two nodes are siblings if they share the same parent. Brothers and sisters in a family tree.
The depth of a node is the number of edges from the root to that node. The root has depth $0$. A child of the root has depth $1$, and so on. Depth tells us how far down a node is from the top.
The height of a node is the number of edges on the longest path from that node down to a leaf. A leaf node has height $0$. The height of the tree is the height of the root node, which equals the maximum depth of any leaf.
Think of a building. Depth is like the floor number counting from the ground floor. Ground floor (root) is floor 0. Going deeper means going higher floor number. Height of a floor is how many floors are still above it (looking downward from that floor). Height of the building is the total number of floors above ground.
The degree of a node is the number of children that node has. A leaf node has degree $0$. In a binary tree, degree can be 0, 1, or 2 at most. The degree of the tree is the maximum degree of any node in the tree.
Full, Complete, and Perfect Binary Tree
A full binary tree is a binary tree where every node has either $0$ children or exactly $2$ children. No node has exactly $1$ child. Think of it as, every internal node must be completely paired, like a bracket tournament where every match has exactly two players.
A complete binary tree is a binary tree where all levels are completely filled, except possibly the last level. The last level must be filled from left to right, with no gaps in the middle. Think of filling seats in a cinema row by row, from left to right, without leaving any empty seat between occupied ones.
A perfect binary tree is a binary tree where all internal nodes have exactly 2 children, and all leaf nodes are at the same level. It is the most regular shape. A perfect binary tree with height $h$ has exactly $2^{h+1} - 1$ total nodes.
In a full binary tree, if the number of internal nodes is $I$ and the number of leaf nodes is $L$, then \[ L = I + 1 \] This is a very useful and frequently tested property. No matter what shape the full binary tree is, the number of leaves is always exactly one more than the number of internal nodes. Intuition: every time we add an internal node (which contributes 2 children but removes itself from being a leaf), the leaf count increases by exactly 1.
In the full binary tree above with nodes A, B, C, D, E, F, G:
Internal nodes (have children): A, B, C. So $I = 3$.
Leaf nodes (no children): D, E, F, G. So $L = 4$.
Check: $L = I + 1 \Rightarrow 4 = 3 + 1$. Correct.
Array Representation of a Binary Tree
A binary tree can be stored in a plain array without using any pointers. We number the nodes level by level, left to right, starting from index 1. The root is at index 1. For any node at index $i$:
Its parent is at index $\lfloor i/2 \rfloor$
Its left child is at index $2i$
Its right child is at index $2i + 1$
This is exactly the structure used in heaps, and it works best for complete or perfect binary trees, because sparse trees waste many array slots.
For node at index 4 (value 40):
Parent: $\lfloor 4/2 \rfloor = 2$ $\to$ index 2 has value 20. Correct, 40's parent is 20.
Left child: $2 \times 4 = 8$ $\to$ index 8 has value 80. Correct.
Right child: $2 \times 4 + 1 = 9$ $\to$ index 9 has value 90. Correct.
class BinaryTreeArray:
def __init__(self, maxsize):
self.arr = [None] * (maxsize + 1) # 1-indexed
self.maxsize = maxsize
def get_parent(self, i):
if i <= 1:
return None # root has no parent
return self.arr[i // 2]
def get_left_child(self, i):
if 2 * i > self.maxsize:
return None
return self.arr[2 * i]
def get_right_child(self, i):
if 2 * i + 1 > self.maxsize:
return None
return self.arr[2 * i + 1]
# --- Driver Code ---
t = BinaryTreeArray(9)
vals = [None, 10, 20, 30, 40, 50, 60, 70, 80, 90]
for i in range(1, 10):
t.arr[i] = vals[i]
print("Parent of index 4:", t.get_parent(4)) # 20
print("Left child of index 2:", t.get_left_child(2)) # 40
print("Right child of index 2:", t.get_right_child(2)) # 50Binary Tree Formulas
The depth of a node is the number of edges from the root down to that node. The root itself has depth $0$. A child of the root has depth $1$. Each step downward increases depth by $1$.
Simple rule: depth of a node = number of edges you travel starting from the root to reach that node.
Consider the tree with root A, children B and C, where B has children D and E, C has children F and G, D has children H and I, E has child J, F has child K, J has children M and N, H has child L, K has child O, O has child P.
A (root): depth = 0
B, C: depth = 1
D, E, F, G: depth = 2
H, I, J, K: depth = 3
L, M, N, O: depth = 4
P: depth = 5
The level of a node is the same as its depth. A level of a tree consists of all nodes that share the same depth value.
Root is at level 0.
All direct children of the root are at level 1.
Their children are at level 2, and so on.
The terms depth and level are used interchangeably for nodes in a binary tree.
The height of a node is the number of edges on the longest path going downward from that node to any leaf below it.
A leaf node has height $= 0$ (no edges going down from it).
The height of the tree is the height of the root node.
Height of tree = maximum depth of any leaf in the tree.
Think of it this way: depth measures how far down you are from the top. Height measures how far down you can still go from a given node.
Using the same tree as before:
P (a leaf): height = 0
O (parent of P): height = 1
K (parent of O): height = 2
F (parent of K): height = 3
C (parent of F and G): height = 4
A (root): height = 5 (longest path: A $\to$ C $\to$ F $\to$ K $\to$ O $\to$ P)
Height of this tree = 5.
If a tree has height $h$, then the root is at level 0 and the deepest leaf is at level $h$. So the total number of levels is: \[ \text{Total levels } L = h + 1 \] Equivalently, if we know the number of levels $L$, then the height is $h = L - 1$.
The tree above has height $h = 5$. Total levels $= 5 + 1 = 6$ (levels 0, 1, 2, 3, 4, 5). If someone says a tree has 8 levels, the height is $8 - 1 = 7$.
In a binary tree, each node can have at most 2 children. So the number of nodes at each level can at most double compared to the level above it.
Level 0 (root): at most $1 = 2^0$ node
Level 1: at most $2 = 2^1$ nodes
Level 2: at most $4 = 2^2$ nodes
Level $l$: at most $2^l$ nodes
\[ \boxed{\text{Maximum nodes at level } l = 2^l} \]
At level 0: max $2^0 = 1$ node (the root).
At level 3: max $2^3 = 8$ nodes.
At level 10: max $2^{10} = 1024$ nodes.
To get the maximum total nodes in a binary tree of height $h$, we sum the maximum nodes over all levels from 0 to $h$: \[ \sum_{l=0}^{h} 2^l = 2^0 + 2^1 + \cdots + 2^h = 2^{h+1} - 1 \] \[ \boxed{\text{Maximum total nodes for height } h = 2^{h+1} - 1} \] If the total number of levels is $L = h+1$, this can also be written as $2^L - 1$.
This maximum is achieved only by a perfect binary tree, where every level is completely filled.
Height $h = 2$: max nodes $= 2^{2+1} - 1 = 7$.
Height $h = 4$: max nodes $= 2^{4+1} - 1 = 31$.
Height $h = 10$: max nodes $= 2^{11} - 1 = 2047$.
The minimum number of nodes in a binary tree of height $h$ occurs when the tree is as sparse as possible. This happens in a skewed (degenerate) tree, where every internal node has exactly one child, making the tree look like a chain. In this case, each level has exactly one node, so: \[ \boxed{\text{Minimum total nodes for height } h = h + 1} \]
Height $h = 3$: min nodes $= 3 + 1 = 4$ (a straight chain of 4 nodes).
Height $h = 7$: min nodes $= 7 + 1 = 8$.
A right-skewed tree with 4 nodes: root $\to$ child $\to$ grandchild $\to$ great-grandchild. Each node has only one child. Height = 3, nodes = 4.
Given $n$ nodes in a binary tree, the height $h$ is constrained from both sides:
Minimum height (achieved by a complete/perfect-shaped tree, packed as wide as possible): \[ h_{\min} = \lceil \log_2(n+1) \rceil - 1 \]
Maximum height (achieved by a fully skewed tree, one node per level): \[ h_{\max} = n - 1 \]
So for any binary tree with $n$ nodes: \[ \lceil \log_2(n+1) \rceil - 1 \;\le\; h \;\le\; n - 1 \]
$h_{\min} = \lceil \log_2(7+1) \rceil - 1 = \lceil 3 \rceil - 1 = 2$ (a perfect tree with 7 nodes has height 2).
$h_{\max} = 7 - 1 = 6$ (a skewed tree with 7 nodes has height 6).
So for 7 nodes: $2 \le h \le 6$.
Formula Practice Problems
In a binary tree (root at level 0), level 5 is completely full. How many nodes are present at level 5 alone?
Solution: Maximum nodes at level $l = 2^l$. So at level 5: $2^5 = 32$ nodes.
What is the maximum number of nodes possible in a binary tree of height 6?
Solution: Max total nodes $= 2^{h+1} - 1 = 2^{6+1} - 1 = 2^7 - 1 = 128 - 1 = 127$ nodes. This is achieved only by a perfect binary tree.
A binary tree has height 5. What is the minimum number of nodes it can have?
Solution: Min total nodes $= h + 1 = 5 + 1 = 6$ nodes. This occurs in a fully skewed tree where each internal node has exactly one child.
A complete binary tree has 511 nodes. What is its height?
Solution: \[ h_{\min} = \lceil \log_2(511 + 1) \rceil - 1 = \lceil \log_2(512) \rceil - 1 = \lceil 9 \rceil - 1 = 9 - 1 = 8 \] We can verify: $2^{8+1} - 1 = 2^9 - 1 = 511$. So 511 nodes form a perfect binary tree of height 8.
A binary tree has 12 nodes. What is the maximum possible height of this tree?
Solution: Max height $= n - 1 = 12 - 1 = 11$. This occurs in a fully skewed tree where every node has only one child, forming a chain of 12 nodes.
A binary tree has exactly 7 levels (root at level 0 through level 6). What is its height, and what is the maximum number of nodes it can contain?
Solution:
Height $= L - 1 = 7 - 1 = 6$.
Max nodes $= 2^L - 1 = 2^7 - 1 = 128 - 1 = 127$.
A binary tree has $n = 100$ nodes. Which of the following statements about its height $h$ is always true?
(A) $h = 99$ always (B) $6 \le h \le 99$ (C) $h \ge 100$ (D) $h \le 6$ always
Solution:
$h_{\min} = \lceil \log_2(101) \rceil - 1 = \lceil 6.66 \rceil - 1 = 7 - 1 = 6$.
$h_{\max} = n - 1 = 99$.
So height $h$ satisfies $6 \le h \le 99$. The correct answer is (B).
Option A is wrong because $h = 99$ is only the maximum, not always true. Option D is wrong because $h$ can be much larger than 6. Option C is impossible since $h$ can never exceed $n-1 = 99$.
Theorems and Structural Properties of Binary Trees
Level ($l$): Distance from the root node. Root is at level $l = 0$.
Height ($h$): Maximum level of any leaf node in the tree. $h = L - 1$.
Levels Count ($L$): Total number of levels present. $L = h + 1$.
$n$: Total number of nodes in the tree.
$I$: Number of internal nodes (nodes with at least one child).
$n_{\text{leaf}}$: Number of leaf nodes (nodes with no children).
Always: $n = I + n_{\text{leaf}}$.
Full Binary Tree
A full binary tree (also called a strictly binary tree or proper binary tree) is a binary tree where every node has either exactly 0 children or exactly 2 children. No node in a full binary tree has exactly 1 child.
Think of a tournament bracket: every match either ends (leaf) or produces two more matches (internal node). There is never a match with only one continuation.
Derivation of Full Binary Tree Formulas
In any full binary tree: $n_{\text{leaf}} = I + 1$.
Proof using handshaking on edges: In a binary tree with $n$ nodes, there are $n - 1$ edges total (tree property). Each internal node contributes exactly 2 edges going downward (since every internal node in a full binary tree has exactly 2 children). So total edges $= 2I$. But total edges $= n - 1$. Therefore $2I = n - 1$, which gives $n = 2I + 1$. Since $n = I + n_{\text{leaf}}$, we get $I + n_{\text{leaf}} = 2I + 1$, so $n_{\text{leaf}} = I + 1$.
In the full binary tree above: nodes A, B, C, D are internal ($I = 4$). Nodes E, F, G, H, I are leaves ($n_{\text{leaf}} = 5$). Check: $n_{\text{leaf}} = I + 1 \Rightarrow 5 = 4 + 1$. Correct. Also $n = 2I + 1 = 9$ and $I = (n-1)/2 = 4$.
For a full binary tree with $L$ levels:
Minimum nodes: When the tree is a skewed-but-full structure. The minimum has 1 internal node per level except the last, giving a chain of paired leaves. The minimum is $n_{\min} = 2L - 1$. (Each internal level adds 1 internal node and we have $L-1$ internal levels, plus $L$ leaf nodes... actually derived as: $L-1$ internal nodes plus $L$ leaves = $2L - 1$.)
Maximum nodes: When the tree is a perfect binary tree. $n_{\max} = 2^L - 1$.
\[ 2L - 1 \;\le\; n \;\le\; 2^L - 1 \]
Since $L = h + 1$: \[ 2(h+1) - 1 \;\le\; n \;\le\; 2^{h+1} - 1 \Rightarrow 2h + 1 \;\le\; n \;\le\; 2^{h+1} - 1 \]
Minimum total nodes = $2h + 1$ (minimum full binary tree: a left-skewed full tree where each internal node has two children but only the rightmost path is long).
Maximum total nodes = $2^{h+1} - 1$ (perfect binary tree).
Since $n_{\text{leaf}} = I + 1$ and $n = 2I + 1$:
When $n = 2L-1$ (minimum): $I = L - 1$ (minimum internal nodes).
When $n = 2^L - 1$ (maximum): $I = 2^{L-1} - 1$ (maximum internal nodes).
\[ L - 1 \;\le\; I \;\le\; 2^{L-1} - 1 \text{or equivalently} h \;\le\; I \;\le\; 2^h - 1 \]
Example 1: A full binary tree has 15 nodes. Find $I$ and $n_{\text{leaf}}$. \[ I = \frac{n-1}{2} = \frac{15-1}{2} = 7, n_{\text{leaf}} = I+1 = 8 \]
Example 2: A full binary tree has height $h = 3$. What are the minimum and maximum possible total nodes? \[ n_{\min} = 2h+1 = 7, n_{\max} = 2^{h+1}-1 = 15 \]
Example 3: A full binary tree has 9 leaf nodes. How many internal nodes does it have? \[ n_{\text{leaf}} = I + 1 \Rightarrow 9 = I + 1 \Rightarrow I = 8, n = 2I+1 = 17 \]
Perfect Binary Tree
A perfect binary tree is a binary tree where:
Every internal node has exactly 2 children (full condition), AND
All leaf nodes are at the same level (complete and symmetric).
A perfect binary tree of height $h$ has exactly $h+1$ levels, all levels are completely filled. It is the most regular and most densely packed binary tree shape.
Derivation of Perfect Binary Tree Formulas
In a perfect binary tree of height $h$ (or $L$ levels), every level is full. The number of nodes at level $l$ is exactly $2^l$. Summing all levels: \[ n = \sum_{l=0}^{h} 2^l = 2^0 + 2^1 + \cdots + 2^h = 2^{h+1} - 1 \] Or equivalently in terms of levels $L = h+1$: \[ \boxed{n = 2^{h+1} - 1 = 2^L - 1} \]
All leaf nodes are at the last level $h$. Number of nodes at level $h$ is $2^h$. \[ \boxed{n_{\text{leaf}} = 2^h = 2^{L-1}} \] Since $n = 2^{h+1} - 1$ and $n_{\text{leaf}} = 2^h$: \[ n_{\text{leaf}} = \frac{n+1}{2} \]
$I = n - n_{\text{leaf}} = (2^{h+1} - 1) - 2^h = 2^h - 1$. Also from the full binary tree result ($n = 2I + 1$): \[ I = \frac{n-1}{2} = \frac{2^{h+1} - 2}{2} = 2^h - 1 = 2^{L-1} - 1 \] \[ \boxed{I = 2^h - 1 = 2^{L-1} - 1} \]
From $n = 2^{h+1} - 1$, solving for $h$: \[ n + 1 = 2^{h+1} \Rightarrow h + 1 = \log_2(n+1) \Rightarrow h = \log_2(n+1) - 1 \] This is only valid when $n+1$ is a power of 2 (i.e., the tree is perfect).
Example 1: A perfect binary tree has height $h = 4$. Find $n$, $I$, $n_{\text{leaf}}$. \[ n = 2^{4+1} - 1 = 31, n_{\text{leaf}} = 2^4 = 16, I = 2^4 - 1 = 15 \] Verify: $n_{\text{leaf}} = I + 1 \Rightarrow 16 = 15 + 1$ \checkmark, $n = I + n_{\text{leaf}} = 15 + 16 = 31$ \checkmark
Example 2: A perfect binary tree has 63 nodes. What is its height? \[ h = \log_2(63+1) - 1 = \log_2(64) - 1 = 6 - 1 = 5 \]
Example 3: A perfect binary tree has 5 levels ($L = 5$). Find $n$, $n_{\text{leaf}}$, $I$. \[ n = 2^5 - 1 = 31, n_{\text{leaf}} = 2^{5-1} = 16, I = 2^{5-1} - 1 = 15 \]
Complete Binary Tree
A complete binary tree is a binary tree where:
All levels except possibly the last level are completely filled.
The last level has nodes filled from left to right with no gaps in between.
A perfect binary tree is always also a complete binary tree. But a complete binary tree is not always perfect (the last level may be partially filled). Complete binary trees are important because they are efficiently stored in arrays using index formulas.
Derivation of Complete Binary Tree Formulas
A complete binary tree of height $h$ has all levels 0 to $h-1$ completely filled ($2^h - 1$ nodes in them), and level $h$ has at least 1 node and at most $2^h$ nodes. Therefore: \[ \underbrace{(2^h - 1) + 1}_{=\;2^h} \;\le\; n \;\le\; \underbrace{(2^h - 1) + 2^h}_{=\;2^{h+1}-1} \] \[ \boxed{2^h \;\le\; n \;\le\; 2^{h+1} - 1} \] Equivalently in terms of levels $L$: \[ \boxed{2^{L-1} \;\le\; n \;\le\; 2^L - 1} \]
From $2^h \le n \le 2^{h+1} - 1$, taking $\log_2$ of the lower bound: \[ h = \lfloor \log_2 n \rfloor \] This is the exact height formula for any complete binary tree with $n$ nodes.
For a complete binary tree with $n$ nodes: \[ \boxed{n_{\text{leaf}} = \left\lceil \frac{n}{2} \right\rceil} \] \[ \boxed{I = \left\lfloor \frac{n}{2} \right\rfloor} \]
Derivation: Using the array representation (1-indexed), nodes $\lfloor n/2 \rfloor + 1$ through $n$ are leaves (they have no children since their left child would be at index $> n$). That is $n - \lfloor n/2 \rfloor = \lceil n/2 \rceil$ leaves. The remaining $\lfloor n/2 \rfloor$ nodes are internal.
Checking the formula:
If $n = 9$: $n_{\text{leaf}} = \lceil 9/2 \rceil = 5$, $I = \lfloor 9/2 \rfloor = 4$.
If $n = 10$: $n_{\text{leaf}} = \lceil 10/2 \rceil = 5$, $I = \lfloor 10/2 \rfloor = 5$.
In a complete binary tree stored in a 1-indexed array of size $n$:
Node at index $i$ has left child at $2i$ and right child at $2i+1$.
A node at index $i$ is a leaf if $2i > n$ (its left child doesn't exist).
Largest non-leaf index: $\lfloor n/2 \rfloor$.
Indices $\lfloor n/2 \rfloor + 1$ to $n$ are all leaves: that is $n - \lfloor n/2 \rfloor = \lceil n/2 \rceil$ leaf nodes.
All levels $0$ to $L-2$ are completely full in a complete binary tree. So the minimum number of internal nodes includes all of level $L-2$ and above:
Minimum $I$: when the last level has only 1 node (leftmost), then $I = (2^{L-1} - 1)$ from filled levels... actually the range comes from the range of $n$:
Since $I = \lfloor n/2 \rfloor$ and $2^{L-1} \le n \le 2^L - 1$:
\[ \left\lfloor \frac{2^{L-1}}{2} \right\rfloor \;\le\; I \;\le\; \left\lfloor \frac{2^L - 1}{2} \right\rfloor \Rightarrow 2^{L-2} \;\le\; I \;\le\; 2^{L-1} - 1 \] In terms of height $h$: \[ \boxed{2^{h-1} \;\le\; I \;\le\; 2^h - 1} \]
Example 1: A complete binary tree has 20 nodes. Find $h$, $n_{\text{leaf}}$, $I$. \[ h = \lfloor \log_2 20 \rfloor = \lfloor 4.32 \rfloor = 4 \] \[ n_{\text{leaf}} = \lceil 20/2 \rceil = 10, I = \lfloor 20/2 \rfloor = 10 \] Verify: $n_{\text{leaf}} + I = 10 + 10 = 20 = n$ \checkmark
Example 2: A complete binary tree has height $h = 3$. What are the minimum and maximum nodes? \[ n_{\min} = 2^3 = 8, n_{\max} = 2^{3+1} - 1 = 15 \]
Example 3: A complete binary tree has 100 nodes. Find $n_{\text{leaf}}$ and $I$. \[ n_{\text{leaf}} = \lceil 100/2 \rceil = 50, I = \lfloor 100/2 \rfloor = 50 \]
Example 4: A complete binary tree has 7 nodes (hence perfect). Find $n_{\text{leaf}}$ using the complete tree formula. \[ n_{\text{leaf}} = \lceil 7/2 \rceil = 4 = 2^2 = 2^{h} \text{ (since } h = \lfloor \log_2 7 \rfloor = 2\text{)} \] Both complete and perfect formulas agree here. \checkmark
Binary Tree Traversals
Traversal means visiting every node of the tree exactly once, in some specific order. Unlike arrays where we always go from index 0 to $n-1$, trees can be traversed in many different orders. The four common traversals are Inorder, Preorder, Postorder, and Level-order. Each gives a different sequence of nodes, and each is useful for different purposes.
Inorder Traversal (Left, Root, Right)
In inorder traversal, we visit nodes in the order: Left subtree, then Root, then Right subtree, recursively. Think of it as reading a book: go all the way to the leftmost page first, read it, come back, read the current chapter, then go to the right. For a BST, inorder traversal gives nodes in sorted order, which is a very important property.
Preorder Traversal (Root, Left, Right)
In preorder traversal, we visit nodes in the order: Root first, then Left subtree, then Right subtree. Think of it as copying a directory structure: you first note down the current folder name, then copy everything inside the left subfolder, then copy everything inside the right subfolder. Preorder is used to create a copy of the tree.
Postorder Traversal (Left, Right, Root)
In postorder traversal, we visit nodes in the order: Left subtree, then Right subtree, then Root last. Think of it as cleaning up: you clean all the stuff inside a folder first, and only then delete the folder itself. Postorder is used to delete a tree, or to evaluate expression trees where operators come after operands.
Reconstructing a Tree from Two Traversals
Given two traversals, we can reconstruct the unique binary tree, but only if one of them is Inorder. This is because Inorder tells us which nodes are on the left and which are on the right of each root. The other traversal (Preorder or Postorder) tells us which node is the root.
Inorder + Preorder $\to$ can reconstruct unique tree.
Inorder + Postorder $\to$ can reconstruct unique tree.
Preorder + Postorder alone $\to$ cannot always reconstruct unique tree.
Given:
Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]
Step 1: First element of Preorder is always the root. So root = 3.
Step 2: Find root (3) in Inorder. Everything to its left in Inorder ([9]) is in the left subtree. Everything to its right ([15, 20, 7]) is in the right subtree.
Step 3: Left subtree has 1 node (9). Right subtree has 3 nodes (15, 20, 7). Take next 1 element from Preorder for left subtree: [9]. Take next 3 for right subtree: [20, 15, 7].
Step 4: Recurse. For right subtree: Preorder [20, 15, 7], Inorder [15, 20, 7]. Root = 20. Left of 20 in Inorder = [15]. Right = [7].
Final Tree:
Given:
Preorder: [1, 2, 4, 5, 3, 6]
Inorder: [4, 2, 5, 1, 3, 6]
Step 1: Preorder[0] = 1 is the main root.
Step 2: In Inorder, elements left of 1 are [4, 2, 5] (Left subtree), and right of 1 are [3, 6] (Right subtree).
Step 3: For Left subtree: Preorder is [2, 4, 5] and Inorder is [4, 2, 5]. Root = 2. Left of 2 is [4], right of 2 is [5].
Step 4: For Right subtree: Preorder is [3, 6] and Inorder is [3, 6]. Root = 3. Left of 3 is empty, right of 3 is [6].
Final Tree:
Given:
Preorder: [A, B, D, E, C]
Inorder: [D, B, E, A, C]
Step 1: Preorder[0] = A is the root.
Step 2: Inorder splits into Left: [D, B, E] and Right: [C].
Step 3: For Left subtree: Preorder is [B, D, E], Inorder is [D, B, E]. Root = B. Left of B is [D], right of B is [E].
Step 4: For Right subtree: Only node [C] remains as the right child of A.
Final Tree:
Given:
Inorder: [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]
Step 1: Last element of Postorder is always the root. So root = 3.
Step 2: Locate 3 in Inorder. Left subtree nodes = [9], Right subtree nodes = [15, 20, 7].
Step 3: Process Postorder from right to left. Left subtree gets Postorder [9], Right subtree gets Postorder [15, 7, 20].
Step 4: For Right subtree: Last element in Postorder [15, 7, 20] is 20. Root = 20. Left of 20 in Inorder = [15], Right = [7].
Final Tree:
Given:
Inorder: [4, 2, 5, 1, 6, 3]
Postorder: [4, 5, 2, 6, 3, 1]
Step 1: Postorder[-1] = 1 is the main root.
Step 2: Inorder splits into Left: [4, 2, 5] and Right: [6, 3].
Step 3: For Right subtree ([6, 3]): Postorder slice is [6, 3]. Last element = 3 (Right child of 1). In Inorder, 6 is to the left of 3.
Step 4: For Left subtree ([4, 2, 5]): Postorder slice is [4, 5, 2]. Last element = 2 (Left child of 1). Left of 2 is [4], Right of 2 is [5].
Final Tree:
Given:
Inorder: [D, B, A, E, C, F]
Postorder: [D, B, E, F, C, A]
Step 1: Postorder[-1] = A is the root.
Step 2: Inorder splits into Left: [D, B] and Right: [E, C, F].
Step 3: For Left subtree: Postorder is [D, B]. Root = B. Inorder shows D is on the left of B.
Step 4: For Right subtree: Postorder is [E, F, C]. Root = C. Inorder shows E is to the left of C, and F is to the right of C.
Final Tree:
When given Preorder and Postorder traversals without Inorder, we can identify the main root (first element of Preorder, last element of Postorder). However, whenever a node has only one child, it is impossible to determine whether that child is a left child or a right child.
General Attempt Method:
Preorder[0] (or Postorder[-1]) is the root.
Preorder[1] is assumed to be the root of the left subtree.
We locate Preorder[1] in Postorder to find the boundary of the left subtree.
Ambiguity: If a parent node has only one child, that child appears immediately after the parent in Preorder and right before it in Postorder, giving no boundary information to distinguish left from right.
Formula for Number of Possible Trees: $$\text{Number of Trees} = 2^k$$ where $k$ is the number of internal nodes with exactly one child. Since each single-child node provides 2 independent choices (Left or Right), $k$ single-child nodes yield $2^k$ possible tree topologies.
Example: Given Preorder: [1, 2, 3] and Postorder: [3, 2, 1].
Node 1 has only child 2 $\to$ Choice of Left or Right.
Node 2 has only child 3 $\to$ Choice of Left or Right.
Here $k = 2$ single-child nodes, so total trees = $2^2 = 4$ distinct topologies.
Given:
Preorder: [1, 2]
Postorder: [2, 1]
Both structures below generate identical Preorder [1, 2] and Postorder [2, 1] sequences:
Given:
Preorder: [1, 2, 3]
Postorder: [3, 2, 1]
Multiple distinct tree topologies satisfy these exact sequences:
Given:
Preorder: [1, 2, 4, 3]
Postorder: [4, 2, 3, 1]
Root is 1. Left subtree contains 2 and 4; Right subtree contains 3. However, whether node 4 is a left child or right child of node 2 cannot be determined:
If additional structural constraints are known, Preorder + Postorder can uniquely reconstruct the tree:
Full / Strict Binary Tree ($k = 0$): Since every internal node has 2 children, no single-child ambiguity exists. $$\text{Number of Trees} = 2^0 = 1 \text{(Unique)}$$
Perfect Binary Tree: A restricted subset of Full Binary Trees. $$\text{Number of Trees} = 1 \text{(Unique)}$$
Complete Binary Tree: Structural position rules force any degree-1 node's single child to be on the left. $$\text{Number of Trees} = 1 \text{(Unique)}$$
Binary Search Tree (BST)
A Binary Search Tree is a binary tree with a very useful ordering property. For every node in the tree:
All values in the left subtree are strictly less than the node's value.
All values in the right subtree are strictly greater than the node's value.
This property holds recursively for every node, not just the root. This ordering makes searching, insertion, and deletion much faster than in a plain binary tree, in the average case.
Think of searching for a word in a dictionary. You open to the middle page. If your word comes before the middle word alphabetically, you look in the left half. Otherwise, you look in the right half. A BST works the same way. At each node, you decide to go left (smaller) or right (larger), eliminating half the remaining nodes each time.
Construct a BST from a Given Insertion Sequence
To construct a BST from a given sequence of keys, we insert them one by one in the given order. The first key becomes the root. Each subsequent key is inserted using the standard BST insert procedure. The shape of the final BST depends entirely on the order of insertion, even if the set of keys is the same.
We insert each number one by one.
def build_bst(sequence):
root = None
for val in sequence:
root = bst_insert(root, val)
return root
def print_tree(root, level=0, prefix="Root: "):
if root:
print(" " * (level * 4) + prefix + str(root.data))
if root.left or root.right:
if root.left:
print_tree(root.left, level + 1, "L: ")
else:
print(" " * ((level+1)*4) + "L: None")
if root.right:
print_tree(root.right, level + 1, "R: ")
else:
print(" " * ((level+1)*4) + "R: None")
# --- Driver Code ---
seq = [5, 3, 7, 1, 4, 6, 8]
root = build_bst(seq)
print("BST built from:", seq)
print_tree(root)
print("\nInorder (sorted):", end=" ")
inorder(root)
# Output:
# Root: 5
# L: 3
# L: 1
# R: 4
# R: 7
# L: 6
# R: 8
# Inorder (sorted): 1 3 4 5 6 7 8
Search in BST
To search for a value in a BST, we start at the root. If the value equals the root, we found it. If the value is less, we go to the left subtree. If more, we go right. We keep doing this until we find the node or reach NULL. At each step, we eliminate one entire subtree from consideration. The time taken is $O(h)$, where $h$ is the height of the tree.
Insert in BST
Inserting a new key follows the same path as search. We search for the key. When we reach NULL (a position where the key would be if it existed), we insert the new node there. We never change existing nodes. We only attach a new leaf. This also takes $O(h)$ time.
Inorder Successor and Predecessor
The inorder successor of a node is the node that comes immediately after it in the inorder traversal. In BST terms, it is the smallest value that is still greater than the node's value.
Case 1: Node has a right subtree. The inorder successor is the leftmost node in the right subtree. We go right once, then keep going left until we cannot go further.
Case 2: Node has no right subtree. The inorder successor is the lowest ancestor for which this node lies in the ancestor's left subtree. We go up the tree until we take a left turn.
The inorder predecessor of a node is the node that comes immediately before it in inorder traversal. It is the largest value still smaller than the node's value.
Case 1: Node has a left subtree. The inorder predecessor is the rightmost node in the left subtree. We go left once, then keep going right until we cannot go further.
Case 2: Node has no left subtree. The inorder predecessor is the lowest ancestor for which this node lies in the ancestor's right subtree. We go up the tree until we take a right turn.
Using the BST with inorder sequence: 20, 30, 35, 40, 50, 60, 70, 80.
Inorder Successors:
Successor of 20: 20 has no right child. Go up. 30 is an ancestor and 20 is in 30's left subtree. So successor of 20 = 30.
Successor of 50: 50 is root and has right subtree. Leftmost in right subtree (rooted at 70): go right to 70, then left to 60. No more left. Successor of 50 = 60.
Successor of 80: 80 has no right child. Go up. 80 is in 70's right subtree. Go up more. 70 is in 50's right subtree. Go up more. 50 is root, no more ancestors. Successor of 80 = NULL (80 is the largest).
Inorder Predecessors:
Predecessor of 50: 50 has left subtree. Rightmost in left subtree (rooted at 30): go left to 30, then right to 40, then right would be... 40 has no right child. Predecessor of 50 = 40.
Predecessor of 20: 20 has no left child. Go up. 20 is in 30's left subtree, so 30 is NOT the answer (we need a right-turn ancestor). Go up more. 30 is in 50's left subtree. Still no. 50 has no parent. Predecessor of 20 = NULL (20 is the smallest).
Predecessor of 60: 60 has no left child. Go up. 60 is in 70's left subtree, so 70 is NOT the answer. Go up. 70 is in 50's right subtree. So predecessor of 60 = 50.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inorder_successor(root, target_val):
"""
Returns the node with the smallest value
greater than target_val in the BST.
Returns None if no successor exists.
"""
curr = root
successor = None
while curr:
if curr.data > target_val:
successor = curr # curr is a valid candidate
curr = curr.left # try to find smaller valid one
elif curr.data < target_val:
curr = curr.right
else: # found the target node
if curr.right:
# Case 1: right subtree exists
# successor = leftmost node in right subtree
temp = curr.right
while temp.left:
temp = temp.left
return temp
break # Case 2: use the stored successor
return successor
def inorder_predecessor(root, target_val):
"""
Returns the node with the largest value
less than target_val in the BST.
Returns None if no predecessor exists.
"""
curr = root
predecessor = None
while curr:
if curr.data < target_val:
predecessor = curr # curr is a valid candidate
curr = curr.right # try to find larger valid one
elif curr.data > target_val:
curr = curr.left
else: # found the target node
if curr.left:
# Case 1: left subtree exists
# predecessor = rightmost node in left subtree
temp = curr.left
while temp.right:
temp = temp.right
return temp
break # Case 2: use the stored predecessor
return predecessor
# ============================================================
# Helper: build BST from insertion sequence
# ============================================================
def insert(root, val):
if root is None:
return Node(val)
if val < root.data:
root.left = insert(root.left, val)
elif val > root.data:
root.right = insert(root.right, val)
return root
# --- Driver Code ---
# Build BST: 50, 30, 70, 20, 40, 60, 80, 35
root = None
for val in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, val)
# Inorder: 20, 30, 35, 40, 50, 60, 70, 80
# Successors
for val in [20, 30, 40, 50, 80]:
s = inorder_successor(root, val)
print(f"Successor of {val}: {s.data if s else 'NULL'}")
print()
# Predecessors
for val in [20, 30, 50, 60, 80]:
p = inorder_predecessor(root, val)
print(f"Predecessor of {val}: {p.data if p else 'NULL'}")
# Output:
# Successor of 20: 30
# Successor of 30: 35
# Successor of 40: 50
# Successor of 50: 60
# Successor of 80: NULL
#
# Predecessor of 20: NULL
# Predecessor of 30: 20
# Predecessor of 50: 40
# Predecessor of 60: 50
# Predecessor of 80: 70Both inorder successor and inorder predecessor algorithms follow a single root-to-node path in the BST, then at most one more root-to-leaf path inside a subtree.
Time Complexity: $O(h)$ where $h$ is the height of the BST.
Case 1 (subtree exists): We first search for the target node going down the BST: $O(h)$ steps. Then we find the leftmost (or rightmost) node in the subtree: at most $O(h)$ additional steps. Total: $O(h)$.
Case 2 (no subtree): We traverse from root to the target node while recording ancestor candidates. This is a single top-down pass: $O(h)$ steps.
Space Complexity: $O(1)$ for the iterative version (only a few pointer variables used). $O(h)$ for a recursive version due to the call stack.
In terms of $n$ (number of nodes):
Best case (balanced BST): $h = O(\log n)$, so time $= O(\log n)$.
Worst case (skewed BST): $h = O(n)$, so time $= O(n)$.
Delete in BST: Three Cases
Deleting a node from a BST is the trickiest operation. There are three cases depending on how many children the node to be deleted has.
Case 1: Leaf node (0 children). Simply remove it. Set the parent's pointer to NULL.
Case 2: One child. Replace the node with its only child. Connect the parent directly to the child.
Case 3: Two children. Find the inorder successor (smallest node in the right subtree). Copy the inorder successor's value into the current node. Then delete the inorder successor (which has at most one child, so it falls into Case 1 or Case 2).
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def bst_insert(root, key):
if root is None:
return Node(key)
if key < root.data:
root.left = bst_insert(root.left, key)
elif key > root.data:
root.right = bst_insert(root.right, key)
return root
def bst_search(root, key):
if root is None or root.data == key:
return root
if key < root.data:
return bst_search(root.left, key)
return bst_search(root.right, key)
def find_min(node):
while node.left:
node = node.left
return node
def bst_delete(root, key):
if root is None:
return None
if key < root.data:
root.left = bst_delete(root.left, key)
elif key > root.data:
root.right = bst_delete(root.right, key)
else:
if root.left is None: # Case 1 and 2
return root.right
if root.right is None: # Case 2
return root.left
succ = find_min(root.right) # Case 3
root.data = succ.data
root.right = bst_delete(root.right, succ.data)
return root
def inorder(root):
if root:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# --- Driver Code ---
root = None
for val in [50, 30, 70, 20, 40, 60, 80]:
root = bst_insert(root, val)
print("Inorder (sorted):", end=" ")
inorder(root) # 20 30 40 50 60 70 80
print()
root = bst_delete(root, 30)
print("After deleting 30:", end=" ")
inorder(root) # 20 40 50 60 70 80
print()
node = bst_search(root, 60)
print("Search 60:", node.data if node else "Not found") # 60Inorder Traversal of BST Gives Sorted Order
In a BST, for any node, all left descendants are smaller and all right descendants are larger. Inorder traversal visits left subtree first, then root, then right subtree. Since left is always smaller than root, and root is always smaller than right, the inorder sequence comes out in increasing order automatically. This property is used to sort a list using a BST.
Height of BST: Best and Worst Case
The height of a BST determines the time for search, insert, and delete, all of which are $O(h)$.
Best case (balanced BST): height $= O(\log n)$. This happens when keys are inserted in a way that the tree stays balanced. Operations are $O(\log n)$.
Worst case (skewed BST): height $= O(n)$. This happens when keys are inserted in sorted order (ascending or descending), making the tree degenerate into a linked list. Operations become $O(n)$.
Number of Distinct BSTs: Catalan Numbers
The number of structurally distinct BSTs that can be formed with $n$ distinct keys is the $n$th Catalan number, given by \[ C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\; n!} \] The first few Catalan numbers are: $C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42$.
For $n = 3$ keys $\{1, 2, 3\}$, there are $C_3 = 5$ distinct BSTs.
