Sponsored
Sponsored
This approach uses recursion to traverse the binary tree. Inorder traversal involves visiting the left subtree, the root node, and then the right subtree. The base case for the recursion is to return if the current node is null.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n) due to the recursion stack.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public class TreeNode {
6 int val;
7 TreeNode left;
8 TreeNode right;
9 TreeNode() {}
10 TreeNode(int val) { this.val = val; }
11 TreeNode(int val, TreeNode left, TreeNode right) {
12 this.val = val;
13 this.left = left;
14 this.right = right;
15 }
16 }
17
18 public List<Integer> inorderTraversal(TreeNode root) {
19 List<Integer> result = new ArrayList<>();
20 inorder(root, result);
21 return result;
22 }
23
24 private void inorder(TreeNode root, List<Integer> result) {
25 if (root == null) return;
26 inorder(root.left, result);
27 result.add(root.val);
28 inorder(root.right, result);
29 }
30}The Java solution uses a helper method named inorder which takes the current node and a list to store the values. We recursively visit the left child, root node, and right child in that order to gather values in the list.
In this approach, we use a stack to perform an iterative inorder traversal. The stack is utilized to track the nodes to be visited. This method mimics the recursive behavior by explicitly using a stack to push left children until reaching a null entry, then processes the nodes and explores the right subtrees.
Time Complexity: O(n)
Space Complexity: O(n)
1
The C implementation employs a manual stack data structure to facilitate the iterative traversal. Nodes are pushed onto the stack until null is reached, allowing us to backtrack, visit the node, and repeat the process for the right subtree.