Non-Linear Data Structures
Binary Trees
A hierarchical structure where every node has at most two children: left and right.
1Introduction
Trees represent hierarchy — folders, organisation charts, HTML documents, expression parse trees. Binary trees, with at most two children per node, are the starting point for BSTs, heaps, segment trees and tries.
2What is it?
A binary tree is either empty or a node holding a value plus a left subtree and a right subtree, each of which is again a binary tree. The top node is the root; nodes without children are leaves.
3Why do we use it?
- Represent hierarchical data naturally.
- Balanced search trees give O(log n) search, insert and delete.
- Recursive structure leads to short, elegant algorithms.
- Heaps (complete binary trees) power priority queues.
4Real-world examples
- File system folders.
- Tournament brackets.
- Expression trees in compilers: (a + b) * c.
- Decision trees in machine learning.
5Internal working
Each node object stores value, left and right references. Missing children are null.
Traversals: preorder (Node-L-R), inorder (L-Node-R), postorder (L-R-Node) use recursion (or a stack); level order uses a queue.
Height h ranges from log₂ n (balanced) to n (skewed), and most operations cost O(h).
6Memory representation
The tree [4, 2, 6, 1, 3, 5, 7] (level order):
4
/ \
2 6
/ \ / \
1 3 5 7
inorder: 1 2 3 4 5 6 7
preorder: 4 2 1 3 6 5 7
postorder: 1 3 2 5 7 6 47Operations
| Operation | How it works |
|---|---|
| Traversal (any order) | Visit each node once. |
| Height / size | Recursive over all nodes. |
| Search (plain binary tree) | May need to check every node. |
| Search (balanced BST) | Go left or right at each level. |
| Insert / delete (balanced BST) | Follow one root-to-leaf path. |
8Visual explanation
Recursively visits the left subtree, then the node itself, then the right subtree (Left → Root → Right). On a Binary Search Tree this produces the values in sorted order.
9Code implementation
Complete, runnable programs (verified in all four languages). JavaScript and Python can be executed in the Coding Playground.
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function inorder(node, result) {
if (node === null) {
return;
}
inorder(node.left, result);
result.push(node.value);
inorder(node.right, result);
}
function buildTree(values) {
if (values.length === 0 || values[0] === null) return null;
const root = new TreeNode(values[0]);
const queue = [root];
let i = 1;
while (queue.length > 0 && i < values.length) {
const node = queue.shift();
if (i < values.length && values[i] !== null) {
node.left = new TreeNode(values[i]);
queue.push(node.left);
}
i++;
if (i < values.length && values[i] !== null) {
node.right = new TreeNode(values[i]);
queue.push(node.right);
}
i++;
}
return root;
}
const root = buildTree([4, 2, 6, 1, 3, 5, 7]);
const result = [];
inorder(root, result);
console.log("Inorder:", result);
10Time complexity
| Operation | Time |
|---|---|
| Traversal (any order) | O(n) |
| Height / size | O(n) |
| Search (plain binary tree) | O(n) |
| Search (balanced BST) | O(log n) |
| Insert / delete (balanced BST) | O(log n) |
11Space complexity
Storing n nodes takes O(n). Recursive algorithms add O(h) call-stack space; level-order traversal needs O(w) queue space where w is the maximum width.
12Advantages
- Models hierarchy directly.
- Fast search when balanced.
- Recursive algorithms are concise.
13Disadvantages
- Can degrade to a linked list (O(n) operations) if unbalanced.
- Pointer overhead per node.
- Recursion can overflow on very deep trees.
14Common mistakes
- Missing the null base case in recursion.
- Confusing the three depth-first orders.
- Assuming a binary tree is a BST.
- Validating a BST by checking only immediate children instead of value ranges.
15Interview questions
16Practice exercises
- Compute the maximum depth of a tree.
- Check whether two trees are identical.
- Invert (mirror) a binary tree.
- Level order traversal returning a list per level.
- Lowest common ancestor of two nodes.
Try them in the Coding Playground.