This pull request introduces a Java implementation of a binary tree boundary traversal algorithm. The primary functionalities include traversing the left boundary, leaf nodes, and the right boundary of the binary tree, while ensuring that no node is traversed more than once. The solution is structured to handle both null nodes and trees with varying structures (complete, incomplete, etc.).
The main components of the algorithm are:
Node Class: A structure representing each node in the binary tree, with data, left, and right pointers.
Solution Class: Implements the boundary traversal logic, broken into:
traverseLeft: Traverses the left boundary, excluding leaf nodes.
traverseLeaf: Traverses all leaf nodes.
traverseRight: Traverses the right boundary, excluding leaf nodes and done in reverse order.
Main Class: Handles input parsing, tree construction, and invoking the Solution.boundary method for output.
The code reads input through a space-separated string, constructs the binary tree, and performs boundary traversal to print the result.
Testing Instructions
The following tests validate the correctness of the boundary traversal logic.
Test Case 1:
Input:
1
1 2 3 4 N 5 6 N N 7 8
Output:
1 2 4 7 8 6 3
This test case checks the traversal of a binary tree with mixed left and right children, validating the correctness of both boundary and leaf node traversal.
Test Case 2:
Input:
1
1 N 2 N 3 N 4 N 5
Output:
1 2 3 4 5
This tests a right-skewed tree, ensuring that the right boundary traversal is correctly handled.
Test Case 3:
Input:
1
1
Output:
1
This test checks the case of a tree with only a root node.
How to Run the Tests
1. Compile the program using:
javac Main.java
2. Run the program:
java Main
3. Provide the input as shown in the test cases. Each test case begins with an integer representing the number of test cases, followed by space-separated strings representing the tree's level-order traversal.
Description
Summary
This pull request introduces a Java implementation of a binary tree boundary traversal algorithm. The primary functionalities include traversing the left boundary, leaf nodes, and the right boundary of the binary tree, while ensuring that no node is traversed more than once. The solution is structured to handle both null nodes and trees with varying structures (complete, incomplete, etc.).
The main components of the algorithm are:
Node Class: A structure representing each node in the binary tree, with data, left, and right pointers.Solution Class: Implements the boundary traversal logic, broken into:traverseLeft: Traverses the left boundary, excluding leaf nodes.traverseLeaf: Traverses all leaf nodes.traverseRight: Traverses the right boundary, excluding leaf nodes and done in reverse order.Main Class: Handles input parsing, tree construction, and invoking the Solution.boundary method for output. The code reads input through a space-separated string, constructs the binary tree, and performs boundary traversal to print the result.Testing Instructions
Test Case 1:
Input:
Output:
This test case checks the traversal of a binary tree with mixed left and right children, validating the correctness of both boundary and leaf node traversal.
Test Case 2:
Input:
Output:
This tests a right-skewed tree, ensuring that the right boundary traversal is correctly handled.
Test Case 3:
Input:
Output:
This test checks the case of a tree with only a root node.
How to Run the Tests
1. Compile the program using:
javac Main.java2. Run the program:
java Main3. Provide the input as shown in the test cases. Each test case begins with an integer representing the number of test cases, followed by space-separated strings representing the tree's level-order traversal.
4. The output will be printed in the console.