Non-Recursive Implementation of Preorder, Inorder, and Postorder Traversals

The three traversal methods—preorder, inorder, and postorder—form the foundation for all tree-related problems.

Preorder Traversal

Algorithm:

1. Create an empty stack and push the root node onto it.
2. While the stack is not empty:
   • Pop a node from the stack and process it (print its value).
   • Push the right child onto the stack first, then the left child.
   • This ensures left nodes are processed before right nodes.

Inorder Traversal

Algorithm:

1. Initialize an empty stack and set a pointer current to the root node.
2. While the stack is not empty or current is not null:
   • If current is not null:
     • Push current onto the stack.
     • Move current to its left child.
   • If current is null:
     • Pop a node from the stack.
     • Process the popped node.
     • Move current to the right child of the popped node.

Postorder Traversal Using Two Stacks

Algorithm:

1. Create two empty stacks, stack1 and stack2.
2. Push the root node onto stack1.
3. While stack1 is not empty:
   • Pop a node from stack1 and push it onto stack2.
   • Push the left child of the popped node onto stack1 if it exists.
   • Push the right child of the popped node onto stack1 if it exists.
4. The nodes popped from stack2 produce the postorder sequence.

Postorder Traversal Using One Stack

Algorithm:

1. Create an empty stack and push the root node onto it.
2. Initialize two pointers: lastVisited to track the most recently processed node, and current to point to the stack top.
3. While the stack is not empty:
   • If the current node's left child exists and hasn't been visited:
     • Push the left child onto the stack.
   • Else if the current node's right child exists and hasn't been visited:
     • Push the right child on to the stack.
   • Else:
     • Pop the node and process it.
     • Update lastVisited to the popped node.

---

Printing Binary Tree Boundary Nodes

Boundary Definition

Approach 1: The boundary consists of the root node, leaf nodes, and the leftmost and rightmost nodes at each level.

Approach 2: The boundary consists of the root node, leaf nodes, and the nodes along the left and right edges of the tree.

Algorithm Using Height Array

1. Compute Tree Height: Perform a recursive traversal to determine the tree height.
2. Store Boundary Nodes: Use an array to store the leftmost and rightmost nodes at each level.
   • During traversal, assign nodes to their respective levels.
3. Print Results:
   • Print the leftmost nodes from top to bottom.
   • Print leaf nodes that are not boundary nodes.
   • Print the rightmost nodes from bottom to top (excluding duplicates).

Algorithm Using Edge Printing Functions

Left Edge Printing:

• Traverse the tree following preorder logic.
• A node belongs to the left boundary if it has no left sibling or if the left child was not printed.

Right Edge Printing:

• Traverse the tree following postorder logic.
• A node belongs to the right boundary if it has no right sibling or if the right child was not printed.

---

Binary Tree Serialization and Deserialization

Preorder Serialization

1. Traverse the tree in preorder.
2. For null nodes, append a placeholder (such as #) to the result string.
3. For non-null nodes, append the node value followed by a delimiter.

Level-Order Serialization

1. Use a queue to perform level-order traversal.
2. For null nodes, append a placeholder to the result.
3. For non-null nodes, append the value and enqueue their children.

Deserialization

1. Parse the serialized string using the delimiter.
2. Reconstruct the tree by reading values in preorder or level-order sequence.

---

Morris Traversal

Morris traversal enables inorder traversal with O(n) time complexity and O(1) space complexity. The technique utilizes null pointers in the tree structure by temporarily creating threads between nodes.

Algorithm for Inorder Morris Traversal:

1. Set current to the root node.
2. While current is not null:
   • If current has no left child:
     • Process current.
     • Move to the right child.
   • Otherwise:
     • Find the rightmost node in current's left subtree (predecessor).
     • If the predecessor's right child is null:
       • Set the predecessor's right child to current.
       • Move current to the left child.
     • Otherwise:
       • Reset the predecessor's right child to null.
       • Process current.
       • Move current to the right child.

---

Longest Path with Given Sum in Binary Tree

Problem Statement

Given a binary tree and an integer target sum, find the length of the longest path where the sum of node values equals target sum. The path must start from some node and proceed downward through child nodes.

Algorithm Using HashMap

1. Create a hashmap pathSumMap where keys represent cumulative sums from root to current node, and values represent the depth at which that sum first occurred.
2. Initialize the hashmap with {0: -1} to handle paths starting from the root.
3. Perform a preorder traversal:
   • Update the cumulative sum.
   • Check if cumulativeSum - targetSum exists in the hashmap.
   • If found, calculate the path length using the depth difference.
   • Store the current cumulative sum if not already present.
   • After processing children, remove the current cumulative sum if it was just added.

The hashmap dynamically tracks path sums, allowing efficient calculation of path lengths. The space complexity is O(h) where h is the tree height.

---

Finding the Largest Binary Search Tree in a Binary Tree

Problem Statement

Given a binary tree where all node values are unique, find the largest subtree that satisfies the binary search tree (BST) property. Return the number of nodes in this largest BST subtree.

Algorithm

1. Define a Record Structure: For each node, store:

   • maxValue: Maximum value in the subtree
   • minValue: Minimum value in the subtree
   • bstSize: Size of the largest BST in this subtree
   • rootIndex: Index of the root of the largest BST

2. Postorder Traversal:

   • Process left and right subtrees first.
   • Determine if the current subtree forms a valid BST:
     • Left subtree must be a BST with all values less than current node.
     • Right subtree must be a BST with all values greater than current node.
   • If valid, update the record with current node as root.
   • Otherwise, return the larger BST between left and right subtrees.

The algorithm runs in O(n) time with O(h) space complexity.

---

Finding the Largest Topological Structure in Binary Tree

Problem Statement

Given a binary tree with unique values, find the largest connected component that satisfies the BST property. The component need not be a complete subtree.

Algorithm

1. Problem Decomposition: Convert the problem to finding the largest BST-like connected component for each node as a potential root.

2. Verification: For each node as the root:

   • Check if a target node can be included in the component by verifying the BST property along the path from root to target.
   • Use recursive traversal to count valid nodes.

3. Optimization: Track the maximum count across all root nodes.

The naive approach has O(n²) time complexity. More efficient solutions using hash-based validation can achieve O(n log n).

---

Level-Order and Zigzag Traversal

Level-Order Traversal

1. Use a queue to process nodes level by level.
2. Track nodesInCurrentLevel and nodesInNextLevel to determine when to print newlines.
3. Process all nodes in the current level before moving to the next.

Zigzag Traversal

1. Use a double-ended queue (deque) instead of a regular queue.
2. Alternate the direction of processing:
   • Left to Right: Dequeue from front, enqueue children at back (left then right).
   • Right to Left: Dequeue from back, enqueue children at front (right then left).
3. Toggle direction after completing each level.

---

Correcting Two Swapped Nodes in BST

Problem Statement

A BST has exactly two nodes swapped, violating the BST property. Identify and output these two nodes in ascending order.

Algorithm

1. Perform inorder traversal to generate the node sequence.
2. In a valid BST, inorder traversal produces a strictly increasing sequence.
3. First Error Node: The larger value in the first pair where the sequence decreases.
4. Second Error Node: The smaller value in the last pair where the sequence decreases.
5. If only one decrease occurs, both error nodes are adjacent in the sequence.

This approach runs in O(n) time with O(1) extra space.

---

Checking Topological Structure Match

Problem Statement

Determine if tree t1 contains a subtree with the same topological structure as tree t2. The match considers connectivity and relative positions, not necessarily identical subtrees.

Algorithm

1. Synchronized Traversal: For each node in t1, check if the structure matches t2 by traversing both trees simultaneously.
2. Comparison Rules:
   • If t2's current node is null, the match succeeds.
   • If t1's current node is null, the match fails.
   • Recursively check left and right subtrees.

The time complexity is O(n × m) where n and m are the sizes of the two trees.

---

Checking Subtree Match

Problem Statement

Determine if tree t1 contains a subtree identical to tree t2. Unlike topological matching, subtree matching requires the matched portion to form a complete subtree.

Method 1: Direct Comparison

1. Traverse t1 and for each node, compare the entire subtree with t2.
2. Ensure the compared subtree in t1 has the same number of nodes as t2 to prevent partial matches.

Method 2: KMP Algorithm

1. Serialize both trees into unique string representations.
2. Use the KMP algorithm to check if t2's string is a substring of t1's string.

---

Checking Balance in Binary Tree

Problem Statement

Determine if a binary tree is balanced. A tree is balanced if for every node, the height difference between left and right subtrees is at most 1.

Algorithm

1. Perform a postorder traversal.
2. For each node, compute the heights of left and right subtrees.
3. Check the height difference: if it exceeds 1, the tree is not balanced.
4. Propagate the maximum height upward while tracking balance status.

The algorithm runs in O(n) time with O(h) space complexity.

---

Constructing BST from Postorder Array

Problem Statement

Given an array of distinct integers representing a postorder traversal, determine if it could be a valid BST postorder sequence.

Algorithm

1. Recursive Validation:

   • The last element is the root.
   • Find the partition point where values exceed the root (beginning of right subtree).
   • Validate that all elements after the partition are greater than root.
   • Recursively validate left and right subarrays.

2. Base Case: A single elemant or empty array is valid.

The recursion ensures the BST property is maintained at each step.

---

Lowest Common Ancestor in Binary Tree

For Binary Search Tree

1. Compare the values of the two target nodes with the current node.
2. If both targets are less than current node, recurse on the left subtree.
3. If both targets are greater than current node, recurse on the right subtree.
4. Otherwise, the current node is the LCA.

For General Binary Tree

1. Perform a postorder traversal.
2. If current node is null or equals either target, return current node.
3. Recursively find LCA in left and right subtrees.
4. If both sides return non-null, current node is the LCA.
5. Otherwise, return the non-null side or null.

Batch LCA Queries

For multiple queries, preprocess the tree:

1. Store parent pointers and depths for each node.
2. For each query:
   • Elevate the deeper node to the same depth.
   • Move both nodes up simultaneously until they meet.

This approach achieves O(n) preprocessing and O(1) per query after preprocessing.

---

Maximum Distance Between Nodes in Binary Tree

Problem Statement

Find the maximum distance (number of edges) between any two nodes in the binary tree.

Algorithm

1. For each node, the maximum distance in its subtree falls into three categories:

   • Maximum distance in the left subtree.
   • Maximum distance in the right subtree.
   • Distance through current node: left height + right height + 1.

2. Postorder Traversal:

   • Compute the height of left and right subtrees.
   • Calculate the distance through current node.
   • Return the maximum distance and height to parent.

The algorithm runs in O(n) time with O(h) space complexity.

---

Constructing Binary Tree from Traversal Sequences

Preorder + Inorder → Postorder

1. The first element in preorder is the root.
2. Find the root's position in inorder to determine left and right subtree sizes.
3. Recursively build left and right subtrees.
4. Generate postorder by concatenating left subtree, right subtree, and root.

Inorder + Postorder → Preorder

1. The last element in postorder is the root.
2. Find the root's position in inorder to partition left and right subtrees.
3. Recursively build left and right subtrees.
4. Generate preorder by concatenating root, left subtree, and right subtree.

Optimization: Use a hashmap to store inorder indices for O(1) lookups.

---

Counting and Generating All Binary Trees

Problem Statement

Given n nodes labeled 1 through n (BST property), count the number of possible binary tree structures.

Dynamic Programming Solution

1. DP Definition: dp[i] represents the number of BST structures with i nodes.
2. Recurrence:
   • For each possible root position k (1 to i):
     • Left subtree has k-1 nodes: dp[k-1] possibilities.
     • Right subtree has i-k nodes: dp[i-k] possibilities.
     • Total for root k: dp[k-1] × dp[i-k].
3. Base Cases:
   • dp[0] = 1 (empty tree).
   • dp[1] = 1 (single node).

The algorithm runs in O(n²) time with O(n) space.

---

Maximum Path Sum in Binary Tree

Problem Statement

Find the maximum path sum where the path can start and end at any nodes but must follow parent-child connections.

Algorithm

1. Postorder Traversal: For each node, compute the maximum path sum ending at that node (path must continue upward).
2. Path Sum Calculation:
   • Maximum path through current node: node.value + max(0, leftSum) + max(0, rightSum).
   • Maximum path ending at current node: node.value + max(0, leftMax) + max(0, rightMax).
3. Track the global maximum path sum during traversal.

The algorithm runs in O(n) time with O(h) space complexity.

---

Tree Representation Methods

Discrete Storage (Pointer-Based)

struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : value(v), left(nullptr), right(nullptr) {}
};

Continuous Storage (Array-Based)

const int MAX_NODES = 100000;
struct Node {
    int data;
    vector<int> children;
} nodes[MAX_NODES];

The array-based representation is particularly useful for competitive programming where node values serve as direct array indices.

Tree Construction from Input

Input Format:

n root
parent leftChild rightChild
...

Construction:

vector<int> tree[MAX_NODES];
void buildTree() {
    int n, root;
    scanf("%d %d", &n, &root);
    for (int i = 0; i < n; ++i) {
        int parent, left, right;
        scanf("%d %d %d", &parent, &left, &right);
        tree[parent].push_back(left);
        tree[parent].push_back(right);
    }
}

---

Data Structures Used

Dynamic Array (Vector)

vector<int> values;
values.push_back(x);      // Append element
values[index];             // Access element

Hash Table (Unordered Map)

unordered_map<int, int> sumMap;
sumMap[key] = value;                    // Insert or update
if (sumMap.find(key) != sumMap.end())   // Check existence
sumMap.erase(key);                      // Remove entry

---

Recursive Function Design Considerations

Reference Parameters vs Return Values

Use Return Values When:

• The result depends solely on the recursive subproblems.
• The calculation follows a natural recursive decomposition.

Use Reference Parameters When:

• Multiple values need to be returned simultaneously.
• Global state must be tracked across recursive calls.
• Real-time updates are required during traversal.

Reference parameters enable efficient tracking of values like maximum distances, heights, and cumulative sums throughout the recursion tree.