🌳 Binary Tree Terminology (Clear & Structured Guide)

A binary tree is a hierarchical data structure where each node has at most two children — usually called left child and right child.

Since you’re comfortable with data structures (given your Git and system-level questions before), I’ll keep this technically precise but clean.

1️⃣ Basic Components

🔹 Node

A fundamental unit of a tree containing:

A value (data)
A left child pointer/reference
A right child pointer/reference

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

🔹 Root

The topmost node of the tree.

Example:

      10
     /  \
    5    20

Here, 10 is the root.

🔹 Parent and Child

If node A connects to node B downward:

A = parent
B = child

In the above example:

10 is parent of 5 and 20
5 and 20 are children of 10

🔹 Siblings

Nodes that share the same parent.

5 and 20 are siblings.

🔹 Leaf Node

A node with no children.

In this tree:

      10
     /  \
    5    20

Nodes 5 and 20 are leaf nodes.

🔹 Internal Node

Any node that is not a leaf.

Here:

10 is an internal node.

2️⃣ Structural Terminology

🔹 Subtree

A node together with all its descendants.

Example: The subtree rooted at 5:

If it had children, they would be included.

🔹 Depth

Number of edges from root to a node.

Example:

      10        (depth 0)
     /  \
    5    20     (depth 1)
         /
        15      (depth 2)

Depth(10) = 0
Depth(15) = 2

🔹 Height

Number of edges in the longest path from a node to a leaf.

Height of a leaf = 0
Height of the tree = height of root

For the above tree:

Height(15) = 0
Height(20) = 1
Height(10) = 2

🔹 Level

Sometimes used interchangeably with depth, but often:

level = depth + 1

Root is level 1.

3️⃣ Types of Binary Trees

🔹 Full Binary Tree

Every node has either 0 or 2 children.

🔹 Complete Binary Tree

All levels are filled except possibly the last, and nodes are filled left to right.

Example:

Used in:

Heaps
Priority queues

🔹 Perfect Binary Tree

All internal nodes have 2 children, and all leaves are at the same level.

Height = h Nodes = 2^(h+1) - 1

🔹 Balanced Binary Tree

Height difference between left and right subtree is small (often ≤ 1 for every node).

Example:

AVL tree
Red-Black tree

🔹 Skewed Tree

All nodes lean to one side.

Left-skewed:

Worst-case height = n Behaves like a linked list.

4️⃣ Special Binary Trees

🔹 Binary Search Tree (BST)

For every node:

left subtree < node < right subtree

Example:

Why important?

Average search: O(log n)
Worst case: O(n) if skewed

🔹 Heap (Binary Heap)

Complete binary tree where:

Min-heap: parent ≤ children
Max-heap: parent ≥ children

5️⃣ Traversal Terminology

Traversal = visiting all nodes in some order.

🔹 DFS Traversals

Inorder (LNR) Left → Node → Right (BST gives sorted order)

Preorder (NLR) Node → Left → Right (used for tree copy)

Postorder (LRN) Left → Right → Node (used for deletion)

Example:

      10
     /  \
    5    20

Inorder: 5, 10, 20
Preorder: 10, 5, 20
Postorder: 5, 20, 10

🔹 BFS (Level Order)

Visit level by level:

10 → 5 → 20

Uses a queue.

from collections import deque

def level_order(root):
    if not root:
        return
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        print(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

6️⃣ Important Mathematical Properties

For a binary tree:

Maximum nodes at level d = 2^d
Maximum nodes in height h tree = 2^(h+1) - 1
Minimum height for n nodes ≈ log₂(n)

7️⃣ Edge Cases to Know (Interview Favorites)

Empty tree (root = None)
Single-node tree
Completely skewed tree
Balanced vs unbalanced height
Null children handling

🎯 Summary Mental Model

Think of binary tree as:

Recursive structure
node
 ├── left subtree
 └── right subtree

Everything — height, traversal, search — is recursive by nature.