Binary Tree Traversal and Properties

1. From Linked Lists to Trees: Basic Terminology

In the last lesson, we saw that a linked list node points to the next node in a sequence. A tree node generalizes this idea: it can point to multiple "next" nodes, which we call its children. This creates a branching, hierarchical structure instead of a linear chain.

Formally, a tree is a collection of nodes connected by edges, with a few key properties:

• It has one special node called the root, which has no parent.
• Every other node has exactly one parent.
• There is a unique path from the root to any other node.

Let's define the essential vocabulary using a diagram:

A sample tree illustrating core terminology. A is the root. B and C are children of A. H, I, J, F, G are leaf nodes. The path from A to K is A -> C -> E -> K. The height of the tree is 4.

• Root: The top-most node of the tree (e.g., A).
• Parent & Child: A node directly connected to another node when moving away from the root. The "from" node is the parent, and the "to" node is the child (e.g., C is the parent of E and F).
• Siblings: Nodes that share the same parent (e.g., E and F).
• Leaf Node: A node with no children (e.g., H, I, J).
• Internal Node: A node that has at least one child (e.g., B, C, E).
• Depth of a Node: The number of edges on the path from the root to that node. The depth of the root is 0.
• Height of a Node: The number of edges on the longest path from that node down to a leaf. The height of a leaf node is 0.
• Height of a Tree: The height of its root node.

Binary Trees

For the GATE syllabus, the most important type of tree is the binary tree. In a binary tree, each node can have at most two children: a left child and a right child.

The node structure in C/C++ is a natural extension of a linked list node:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

2. Tree Traversal: Visiting Every Node

Tree traversal is the process of visiting (e.g., printing the data of) each node in a tree exactly once. There are two main strategies: Depth-First Search (DFS) and Breadth-First Search (BFS).

Depth-First Search (DFS) Traversals

DFS explores as far as possible down one branch before backtracking. The three DFS traversals—preorder, inorder, and postorder—are defined by the relative order in which we visit the root node compared to its left and right subtrees. They are most elegantly implemented using recursion.

The following video from mycodeschool provides an outstanding visual explanation of these three traversals. Pay close attention to the call stack visualization, as it demystifies how recursion works here.

To summarize:

• Preorder (Root-L-R): Useful for getting a prefix expression of an expression tree or for creating a copy of the tree.
• Inorder (L-Root-R): Famously produces a sorted sequence of values from a Binary Search Tree (a topic for our next lesson!).
• Postorder (L-R-Root): Useful for getting a postfix expression or for safely deleting all nodes in a tree (as you process children before the parent).

Breadth-First Search (BFS): Level-Order Traversal

In contrast to DFS, Breadth-First Search explores the tree level by level, visiting all nodes at a given depth before moving to the next. This is known as a level-order traversal.

A while loop and a Queue are the natural tools for implementing level-order traversal, which should be a familiar pattern from your B.Tech courses.

This companion video from mycodeschool explains the queue-based algorithm perfectly.

The algorithm is straightforward:

1. Create an empty queue and add the root node to it.
2. While the queue is not empty:

a. Dequeue a node, let's call it current.
b. Print the data of current.
c. If current has a left child, enqueue it.
d. If current has a right child, enqueue it.

3. Computing Tree Properties

Besides traversal, GATE questions often ask you to compute properties of a given tree. Height and diameter are two of the most common.

Calculating the Height of a Tree

As defined earlier, the height is the longest path from the root to a leaf. We can compute this recursively. The height of a subtree rooted at node is 1 plus the maximum of the heights of its left and right subtrees.

• Base Case: The height of an empty tree (NULL node) is -1. (This makes the height of a single-node tree 1 + max(-1, -1) = 0, which is correct).
• Recursive Step: height(node) = 1 + max(height(node->left), height(node->right))

Calculating the Diameter of a Tree

The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes in the tree. This path may or may not pass through the root. This is a classic and slightly tricky problem.

For any given node, the longest path that involves that node has three possibilities:

1. It lies entirely within the left subtree.
2. It lies entirely within the right subtree.

3. It passes through the current node. In this case, the path length is height(left subtree) + height(right subtree) + 1.

Therefore, a naive recursive function for the diameter at a given node would be:
diameter(node) = max( diameter(node->left), diameter(node->right), 1 + height(node->left) + height(node->right) )

This approach works but is inefficient, as it repeatedly calculates heights, leading to an $O(n^2)$ complexity. A more efficient $O(n)$ solution involves calculating the height and diameter in a single postorder traversal, but understanding the fundamental definition above is the first and most crucial step.

Conclusion

In this lesson, we made the leap from linear to hierarchical data structures. We defined the core vocabulary of trees and then dove deep into the essential traversal algorithms that are fundamental to nearly all tree-based problems.

Key Takeaways:

• Tree Terminology: You should be comfortable with terms like root, child, parent, leaf, height, and depth.
• Binary Tree: A tree where each node has at most two children (left and right).
• DFS Traversals:
  • Preorder (Root-L-R): Defined by visiting the root first.
  • Inorder (L-Root-R): Root is visited between the left and right subtrees.
  • Postorder (L-R-Root): Root is visited last.
  • All are recursive and have $O(n)$ time and $O(h)$ space complexity.
• BFS Traversal (Level-Order): Visits nodes level by level using a queue. It has $O(n)$ time and, in the worst case, $O(n)$ space complexity.
• Tree Properties: Height and Diameter are common computed properties. The diameter is the longest path between any two nodes and can be found recursively.

In our next lesson, we will focus on a special type of binary tree: the Binary Search Tree (BST). We'll see how imposing an ordering constraint on the nodes allows for highly efficient search, insertion, and deletion operations, making it one of the most important data structures in computer science.