Tree
What is a Tree?
A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. It has a root node at the top, and every node (except root) has exactly one parent. Trees are used everywhere — file systems, HTML DOM, databases, compilers, and more.
Tree Terminology
| Term | Definition |
|---|---|
| Root | Top node with no parent |
| Leaf | Node with no children |
| Parent / Child | Direct connection between nodes |
| Sibling | Nodes sharing the same parent |
| Height | Longest path from root to a leaf |
| Depth | Distance from root to a node |
| Subtree | A node and all its descendants |
| Degree | Number of children a node has |
Binary Tree — Traversals
A binary tree is a tree where each node has at most 2 children (left and right). The three main traversal orders are:
- Inorder (L → Root → R) — gives sorted order for BST
- Preorder (Root → L → R) — used to copy/serialize a tree
- Postorder (L → R → Root) — used to delete a tree
- Level-order (BFS) — visits level by level
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};
// Inorder: Left → Root → Right
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
// Preorder: Root → Left → Right
void preorder(Node* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
// Postorder: Left → Right → Root
void postorder(Node* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
// Level-order (BFS)
void levelOrder(Node* root) {
if (!root) return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* node = q.front(); q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
// Height of tree
int height(Node* root) {
if (!root) return 0;
return 1 + max(height(root->left), height(root->right));
}
int main() {
/*
* 1
* / \
* 2 3
* / \
* 4 5
*/
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Inorder: "; inorder(root); cout << endl; // 4 2 5 1 3
cout << "Preorder: "; preorder(root); cout << endl; // 1 2 4 5 3
cout << "Postorder: "; postorder(root); cout << endl; // 4 5 2 3 1
cout << "LevelOrder: "; levelOrder(root); cout << endl; // 1 2 3 4 5
cout << "Height: " << height(root) << endl; // 3
return 0;
}import java.util.*;
public class BinaryTree {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
}
static void inorder(Node root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
static void preorder(Node root) {
if (root == null) return;
System.out.print(root.val + " ");
preorder(root.left);
preorder(root.right);
}
static void postorder(Node root) {
if (root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.val + " ");
}
static void levelOrder(Node root) {
if (root == null) return;
Queue<Node> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
Node node = q.poll();
System.out.print(node.val + " ");
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
}
static int height(Node root) {
if (root == null) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
root.left.left = new Node(4); root.left.right = new Node(5);
System.out.print("Inorder: "); inorder(root); System.out.println();
System.out.print("Preorder: "); preorder(root); System.out.println();
System.out.print("Postorder: "); postorder(root); System.out.println();
System.out.print("LevelOrder: "); levelOrder(root); System.out.println();
System.out.println("Height: " + height(root));
}
}from collections import deque
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root):
if not root: return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root):
if not root: return []
return postorder(root.left) + postorder(root.right) + [root.val]
def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return result
def height(root):
if not root: return 0
return 1 + max(height(root.left), height(root.right))
# Build tree: 1 / 2 3 / 4 5
root = Node(1)
root.left = Node(2); root.right = Node(3)
root.left.left = Node(4); root.left.right = Node(5)
print("Inorder: ", inorder(root)) # [4, 2, 5, 1, 3]
print("Preorder: ", preorder(root)) # [1, 2, 4, 5, 3]
print("Postorder: ", postorder(root)) # [4, 5, 2, 3, 1]
print("LevelOrder:", level_order(root)) # [1, 2, 3, 4, 5]
print("Height: ", height(root)) # 3class Node {
constructor(val) { this.val = val; this.left = null; this.right = null; }
}
function inorder(root, result = []) {
if (!root) return result;
inorder(root.left, result);
result.push(root.val);
inorder(root.right, result);
return result;
}
function preorder(root, result = []) {
if (!root) return result;
result.push(root.val);
preorder(root.left, result);
preorder(root.right, result);
return result;
}
function postorder(root, result = []) {
if (!root) return result;
postorder(root.left, result);
postorder(root.right, result);
result.push(root.val);
return result;
}
function levelOrder(root) {
if (!root) return [];
const result = [], queue = [root];
while (queue.length) {
const node = queue.shift();
result.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return result;
}
function height(root) {
if (!root) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
const root = new Node(1);
root.left = new Node(2); root.right = new Node(3);
root.left.left = new Node(4); root.left.right = new Node(5);
console.log("Inorder: ", inorder(root)); // [4, 2, 5, 1, 3]
console.log("Preorder: ", preorder(root)); // [1, 2, 4, 5, 3]
console.log("Postorder: ", postorder(root)); // [4, 5, 2, 3, 1]
console.log("LevelOrder:", levelOrder(root)); // [1, 2, 3, 4, 5]
console.log("Height: ", height(root)); // 3