Binary Trees and Traversal Orders

A Binary Tree is a specialized tree structure where each node has at most two children, conventionally designated as the left child and right child.

Copy codeclass TreeNode<T>(
    var value: T,
    var left: TreeNode<T>? = null,
    var right: TreeNode<T>? = null
)

The Four Traversal Algorithms

Because linear structures have a single beginning and end, iteration is trivial. Trees, however, can be traversed in multiple distinct orderings.

Copy code        [ 1 ]
       /     \
    [ 2 ]   [ 3 ]
   /    \
 [ 4 ]  [ 5 ]

1. In-Order Traversal (Left → Root → Right)

• Traverse left subtree.
• Visit root.
• Traverse right subtree.
• Result for diagram: 4, 2, 5, 1, 3

Key Property: In a Binary Search Tree (BST), In-Order traversal visits elements in strictly ascending sorted order!

Copy codefun inOrder(root: TreeNode<Int>?) {
    if (root == null) return
    inOrder(root.left)
    print("${root.value} ")
    inOrder(root.right)
}

2. Pre-Order Traversal (Root → Left → Right)

• Visit root first.
• Traverse left subtree.
• Traverse right subtree.
• Result for diagram: 1, 2, 4, 5, 3

Use Case: Cloning or serializing a tree structure (saving tree to disk/JSON).

3. Post-Order Traversal (Left → Right → Root)

• Traverse left subtree.
• Traverse right subtree.
• Visit root last.
• Result for diagram: 4, 5, 2, 3, 1

Use Case: Deleting a tree, computing directory file sizes (children must be evaluated before parent).

4. Level-Order Traversal (Breadth-First Search / BFS)

Visits nodes level by level from top to bottom, left to right.

• Result for diagram: 1, 2, 3, 4, 5
• Implemented iteratively using a Queue:

Copy codefun levelOrder(root: TreeNode<Int>?) {
    if (root == null) return
    val queue = ArrayDeque<TreeNode<Int>>()
    queue.addLast(root)

    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        print("${current.value} ")

        current.left?.let { queue.addLast(it) }
        current.right?.let { queue.addLast(it) }
    }
}

Complexity Summary

(where h is tree height, w is maximum width of the tree)

Summary

• Binary tree nodes have at most two children (left, right).
• DFS traversals: In-Order (L-Root-R), Pre-Order (Root-L-R), Post-Order (L-R-Root).
• BFS traversal: Level-Order visits horizontal layers sequentially using a Queue.