Data StructuresBeginner14 min readUpdated March 2025

Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children (left and right). Trees model hierarchical relationships and enable efficient searching, sorting, and expression parsing.

Binary Tree Terminology

A binary tree is a tree where each node has at most two children. Key terminology:

- Root — The topmost node (no parent) - Leaf — A node with no children - Height — The length of the longest path from root to a leaf - Depth — The distance from the root to a given node - Level — All nodes at the same depth - Subtree — A node and all its descendants

Special types: - Full Binary Tree — Every node has 0 or 2 children - Complete Binary Tree — All levels filled except possibly the last, which is filled left to right - Perfect Binary Tree — All internal nodes have 2 children and all leaves are at the same level - Balanced Binary Tree — Height is O(log n)

Tree Traversals

There are four fundamental ways to traverse a binary tree:

Inorder (Left, Root, Right) — For BSTs, produces elements in sorted order.
Preorder (Root, Left, Right) — Used to copy/serialize a tree.
Postorder (Left, Right, Root) — Used to delete a tree or evaluate expression trees.
Level-order (BFS) — Visits nodes level by level. Uses a queue.

Implementing Binary Tree Traversals

Both recursive and iterative implementations of all four traversals:

python

from collections import deque
from typing import Optional, List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# ---- Recursive Traversals ----
def inorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# ---- Level-Order (BFS) ----
def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

# ---- Iterative Inorder (using explicit stack) ----
def inorder_iterative(root: Optional[TreeNode]) -> List[int]:
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

# Build test tree:     4
#                    /   #                   2     6
#                  /    / #                 1   3 5   7
root = TreeNode(4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(6, TreeNode(5), TreeNode(7))
)

print("Inorder:    ", inorder(root))       # [1,2,3,4,5,6,7]
print("Preorder:   ", preorder(root))      # [4,2,1,3,6,5,7]
print("Postorder:  ", postorder(root))     # [1,3,2,5,7,6,4]
print("Level-order:", level_order(root))   # [[4],[2,6],[1,3,5,7]]

Tree Height, Diameter, and Path Sum

Common tree problems solved with recursion:

python

# ---- Height of Binary Tree ----
def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

# ---- Diameter (longest path between any two nodes) ----
def diameter(root):
    max_diameter = [0]
    def depth(node):
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        max_diameter[0] = max(max_diameter[0], left + right)
        return 1 + max(left, right)
    depth(root)
    return max_diameter[0]

# ---- Check if path sum exists ----
def has_path_sum(root, target):
    if not root:
        return False
    if not root.left and not root.right:   # Leaf node
        return root.val == target
    return (has_path_sum(root.left, target - root.val) or
            has_path_sum(root.right, target - root.val))

print("Height:", height(root))      # 3
print("Diameter:", diameter(root))  # 4 (path: 1-2-4-6-7 or 3-2-4-6-5)

Key Takeaways

Binary trees have at most two children per node; height of a balanced tree is O(log n).
Inorder traversal of a BST produces sorted output; preorder is used for serialization.
Level-order traversal uses a queue (BFS); depth-first traversals use recursion or a stack.
Most tree problems are solved elegantly with recursion — define the base case and recursive case.
A balanced tree has O(log n) height; an unbalanced tree degrades to O(n) for search operations.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com