Explain binary tree traversals and related properties.
Answer:-
A binary tree is either:
- An empty set of nodes, or
- A root node with two disjoint binary trees: left subtree (TL) and right subtree (TR).
It is considered a special case of an ordered tree.
Divide-and-Conquer in Binary Trees
Binary trees naturally follow the divide-and-conquer strategy:
- The root divides the problem into two subproblems: left and right subtree.
- Subproblems are solved recursively.
- The solutions are combined if needed.
Example: Height of a Binary Tree
The height is the longest path from the root to a leaf.
Recursive Algorithm:
ALGORITHM Height(T):
if T = ∅ return -1
else return max{Height(Tleft), Height(Tright)} + 1
The height of an empty tree is defined as -1.
Let n be the number of internal nodes. Then,
- Additions A(n) = n
- Comparisons C(n) = 2n + 1
External Nodes and Extended Binary Tree
To analyze the algorithm, we consider an extended binary tree:
- Add a special external node for each empty subtree.
- Let:
- n = internal nodes
- x = external nodes
Then,
x = n + 1
Proof:
From tree properties,
2n + 1 = x + n ⟹ x = n + 1
Binary Tree Traversals
All three standard tree traversals follow divide-and-conquer:
a) Preorder Traversal
- Visit root
- Traverse left subtree
- Traverse right subtree
b) Inorder Traversal
- Traverse left subtree
- Visit root
- Traverse right subtree
c) Postorder Traversal
- Traverse left subtree
- Traverse right subtree
- Visit root
Efficiency
Each traversal visits every node, including external ones. So:
- Comparisons: 2n + 1
- Additions: n
Special Note
Not all operations require both subtrees.
For example, search and insert in Binary Search Trees (BST) only process one subtree, and follow the variable-size-decrease approach (not divide-and-conquer).