Preorder and Postorder Traversals
Problem Statement
Write a Java program that extends a Binary Search Tree (BST) implementation to include methods for preorder (root, left, right) and postorder (left, right, root) traversals. The program should reuse the BST node structure and print the results of both traversals for sample trees, including balanced, unbalanced, empty, and single-node trees. The traversals should output node values in the respective orders as space-separated strings. You can visualize this as exploring a family tree in two different ways: preorder visits the parent before children, while postorder visits children before the parent, listing their names in the order visited.
Input:
- A BST represented by nodes with integer values. Output: Two strings representing the preorder and postorder traversals of the tree, each containing space-separated node values, or "Empty" for an empty tree. Constraints:
- The tree has between 0 and 10^5 nodes.
- Node values are integers in the range [-10^9, 10^9].
- Duplicate values are not allowed in the BST. Example:
- Input: Tree = [5, left: [3, left: [1], right: [4]], right: [7]]
- Output:
- Preorder: "5 3 1 4 7"
- Postorder: "1 4 3 7 5"
- Explanation: Preorder visits root first (5), then left (3, 1, 4), then right (7); postorder visits left (1, 4), then right (7), then root (5).
- Input: Tree = []
- Output:
- Preorder: "Empty"
- Postorder: "Empty"
- Explanation: Empty tree has no nodes to traverse.
Pseudocode
CLASS Node
SET value to integer
SET left to Node (null by default)
SET right to Node (null by default)
ENDCLASS
FUNCTION preorderTraversal(root)
IF root is null THEN
RETURN "Empty"
ENDIF
CREATE result as new StringBuilder
FUNCTION preorder(node)
IF node is null THEN
RETURN
ENDIF
APPEND node.value and " " to result
CALL preorder(node.left)
CALL preorder(node.right)
ENDFUNCTION
CALL preorder(root)
RETURN result as string trimmed
ENDFUNCTION
FUNCTION postorderTraversal(root)
IF root is null THEN
RETURN "Empty"
ENDIF
CREATE result as new StringBuilder
FUNCTION postorder(node)
IF node is null THEN
RETURN
ENDIF
CALL postorder(node.left)
CALL postorder(node.right)
APPEND node.value and " " to result
ENDFUNCTION
CALL postorder(root)
RETURN result as string trimmed
ENDFUNCTION
FUNCTION main()
SET testCases to array of trees
FOR each testCase in testCases
PRINT test case details
CALL preorderTraversal(testCase.root)
CALL postorderTraversal(testCase.root)
PRINT preorder and postorder results
ENDFOR
ENDFUNCTION
Algorithm Steps
- Reuse the
Nodeclass with: a. An integervalue. b.leftandrightpointers to child nodes. - Define
preorderTraversal: a. If root is null, return "Empty". b. Use a helper function to:- Append node value.
- Recurse on left subtree.
- Recurse on right subtree. c. Return trimmed result string.
- Define
postorderTraversal: a. If root is null, return "Empty". b. Use a helper function to:- Recurse on left subtree.
- Recurse on right subtree.
- Append node value. c. Return trimmed result string.
- In
main, test with: a. A balanced BST. b. An unbalanced (skewed) BST. c. An empty tree. d. A single-node tree.
Java Implementation
public class PreorderPostorderTraversals {
// Node class for the binary search tree
static class Node {
int value;
Node left, right;
Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Performs preorder traversal (root, left, right)
public String preorderTraversal(Node root) {
if (root == null) {
return "Empty";
}
StringBuilder result = new StringBuilder();
preorder(root, result);
return result.toString().trim();
}
private void preorder(Node node, StringBuilder result) {
if (node == null) {
return;
}
result.append(node.value).append(" ");
preorder(node.left, result);
preorder(node.right, result);
}
// Performs postorder traversal (left, right, root)
public String postorderTraversal(Node root) {
if (root == null) {
return "Empty";
}
StringBuilder result = new StringBuilder();
postorder(root, result);
return result.toString().trim();
}
private void postorder(Node node, StringBuilder result) {
if (node == null) {
return;
}
postorder(node.left, result);
postorder(node.right, result);
result.append(node.value).append(" ");
}
// Helper class for test cases
static class TestCase {
Node root;
TestCase(int[] values, int[][] edges) {
if (values.length == 0) {
root = null;
return;
}
Node[] nodes = new Node[values.length];
for (int i = 0; i < values.length; i++) {
nodes[i] = new Node(values[i]);
}
for (int[] edge : edges) {
int parent = edge[0], child = edge[1];
if (edge[2] == 0) {
nodes[parent].left = nodes[child];
} else {
nodes[parent].right = nodes[child];
}
}
root = nodes[0];
}
}
// Main method to test traversals
public static void main(String[] args) {
PreorderPostorderTraversals traverser = new PreorderPostorderTraversals();
// Test cases
TestCase[] testCases = {
// Balanced BST: [5, left: [3, left: 1, right: 4], right: 7]
new TestCase(
new int[]{5, 3, 1, 4, 7},
new int[][]{{0, 1, 0}, {0, 4, 1}, {1, 2, 0}, {1, 3, 1}}
),
// Unbalanced BST: [5, right: [7, right: [9, right: 10]]]
new TestCase(
new int[]{5, 7, 9, 10},
new int[][]{{0, 1, 1}, {1, 2, 1}, {2, 3, 1}}
),
// Empty tree
new TestCase(new int[]{}, new int[][]{}),
// Single node
new TestCase(new int[]{10}, new int[][]{})
};
// Run test cases
for (int i = 0; i < testCases.length; i++) {
System.out.println("Test case " + (i + 1) + ":");
System.out.println("Preorder: " + traverser.preorderTraversal(testCases[i].root));
System.out.println("Postorder: " + traverser.postorderTraversal(testCases[i].root) + "\n");
}
}
}
Output
Running the main method produces:
Test case 1:
Preorder: 5 3 1 4 7
Postorder: 1 4 3 7 5
Test case 2:
Preorder: 5 7 9 10
Postorder: 10 9 7 5
Test case 3:
Preorder: Empty
Postorder: Empty
Test case 4:
Preorder: 10
Postorder: 10
Explanation:
- Test case 1: Balanced BST, preorder visits root (5), left (3, 1, 4), right (7); postorder visits left (1, 4), right (7), root (5).
- Test case 2: Unbalanced (skewed) BST, preorder visits 5, 7, 9, 10; postorder visits 10, 9, 7, 5.
- Test case 3: Empty tree, both traversals return "Empty".
- Test case 4: Single node, both traversals return "10".
How It Works
- Node: Stores an integer value and pointers to left and right children.
- preorderTraversal:
- Returns "Empty" for null root.
- Appends root value, recurses on left, then right.
- postorderTraversal:
- Returns "Empty" for null root.
- Recurses on left, then right, then appends root value.
- Example Trace (Test case 1):
- Preorder: Visit 5, left (3, left (1), right (4)), right (7) → "5 3 1 4 7".
- Postorder: Left (1, 4), right (7), root (5) → "1 4 3 7 5".
- Main Method: Tests balanced BST, unbalanced BST, empty tree, and single node.
Complexity Analysis Table
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| preorderTraversal | O(n) | O(h) |
| postorderTraversal | O(n) | O(h) |
Note:
- n is the number of nodes in the tree.
- h is the height of the tree (O(n) for skewed, O(log n) for balanced).
- Time complexity: O(n) for both traversals (visit each node once).
- Space complexity: O(h) for recursion stack.
- Worst case: O(n) time and O(n) space for skewed trees.
✅ Tip: Use recursive traversal methods for simplicity, as they naturally follow the tree’s structure. Preorder is useful for copying a tree, while postorder is useful for deleting a tree.
⚠ Warning: Handle null nodes to avoid null pointer exceptions. Ensure the output string is trimmed to remove trailing spaces for clean presentation.