Boundary Traversal of Binary Tree

Overview

• Goal: Print the boundary traversal of a binary tree (currently focusing on anti-clockwise traversal).
• Steps: Left boundary (excluding leaves), leaf nodes, right boundary (in reverse, excluding leaves).

Steps to Solve the Problem

1. Left Boundary (Excluding Leaves)

• Start with the root of the tree.
• Include the root in the data structure to store the boundary traversal.
• Move to the left of the root.
  • If the left node is not a leaf, add it to the data structure.
  • If a left node doesn't exist, move to the right node.
  • Continue this until reaching a leaf node, then stop.

2. Leaf Nodes

• Perform an inorder traversal of the tree to fetch leaf nodes.
  • Inorder traversal: Visit left subtree → root → right subtree.
  • Check each node: If it's a leaf node, add it to the data structure.
  • This ensures leaf nodes are captured from left to right.

3. Right Boundary (In Reverse, Excluding Leaves)

• Start with the root's right node.
• Use a stack or vector to store these nodes temporarily.
• Move to the right nodes.
  • Add nodes if they are not leaves.
  • If a right node doesn't exist, move to the left node.
  • Stop at leaf nodes.
• Reverse the stored nodes before adding them to the final boundary traversal to ensure anti-clockwise order.

Algorithm Summary

• Left Boundary: Traverse left, if not left, then right. Exclude leaves.
• Leaf Nodes: Inorder traversal to check for leaf nodes.
• Right Boundary: Traverse right, if not right, then left. Exclude leaves. Reverse order.
• Final Boundary Traversal: Combine results from the above steps.

Code Explanation

C++ and Java Code Overview

1. Initialization: Declare a vector or data structure to store boundary traversal.
2. Root Check: If the root is empty, return an empty data structure.
3. Add Root: If the root is not a leaf, add it to the data structure.
4. Left Boundary:

• Start from root's left.
  • Add nodes to left boundary data structure if not leaves.
  • Move left or right accordingly.

5. Right Boundary:

• Start from root's right.
  • Add nodes to a temporary data structure if not leaves.
  • Move right or left accordingly.
  • Reverse the temporary data structure and append to final result.

6. Leaf Nodes:

• Use inorder traversal to add leaf nodes to the data structure.

7. Combine Results: Merge results from left boundary, leaf nodes, and reversed right boundary.

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree.
  • Left boundary: O(Height of Tree)
  • Right boundary: O(Height of Tree)
  • Inorder traversal: O(N)
• Space Complexity: O(N), considering the space required to store the traversal sequence.

Closing Notes

• Make sure to implement the algorithm correctly in code.
• The provided code examples (C++ and Java) can be useful for reference.
• Remember to like and subscribe to the channel for more content.