Binary trees are fundamental data structures in computer science and are widely used in various applications, from databases to game development. Understanding how to traverse a binary tree is a crucial skill for any programmer, and it often comes up in coding interviews. In this blog post, we will explore the concept of 94.binary tree in order traversal and provide a Java solution for the problem on LeetCode. We’ll break down the problem step by step, explain the algorithm, and provide code examples.
Understanding Binary Trees
Before we delve into binary tree inorder traversal, let’s ensure we have a good understanding of binary trees.
A binary tree is a hierarchical data structure composed of nodes, where each node has at most two child nodes: a left child and a right child. The topmost node in a binary tree is called the root, and nodes without children are referred to as leaves. Each node in the tree holds a value, which can be of any data type.
Here’s a visual representation of a simple binary tree:
1
/ \
2 3
/ \
4 5In this tree, 1 is the root node, and it has two children: 2 and 3. Node 2 has two children, 4 and 5. Nodes 4 and 5 are leaf nodes as they have no children.
Inorder Traversal
Inorder traversal is one of the three commonly used methods to traverse a binary tree. The other two are preorder and postorder traversal. In inorder traversal, you visit the left subtree first, then the root node, and finally the right subtree. The order of traversal is “left, root, right.”
Let’s apply inorder traversal to the binary tree we discussed earlier:
Inorder Traversal: 4, 2, 5, 1, 3As you can see, we start from the leftmost node (4), then move to its parent (2), then to the right child (5), followed by the root (1), and finally the right subtree’s root (3).
In programming, inorder traversal is often implemented using recursion or an explicit stack. We will explore both methods in the context of a LeetCode problem.
LeetCode Problem: Binary Tree Inorder Traversal
LeetCode is a popular platform for practicing coding problems and algorithms. The problem we’ll tackle here is known as “Binary Tree Inorder Traversal” (Problem #94). The problem statement is as follows:
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example
Let’s take an example to illustrate the problem. Consider the following binary tree:
1
\
2
/
3The inorder traversal of this tree is [1, 3, 2].
Approach 1: Recursive Solution
One way to solve this problem is by using a recursive approach. We will create a helper function that performs the inorder traversal and collects the node values into a list.
Here’s the Java code for this approach:
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeInorderTraversal {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node != null) {
inorderHelper(node.left, result);
result.add(node.val);
inorderHelper(node.right, result);
}
}
}In this code, we define a TreeNode class to represent the nodes of the binary tree. The inorderTraversal method is the entry point for our solution. It initializes an empty list called result to store the node values and then calls the inorderHelper function to perform the actual traversal.
The inorderHelper function is a recursive function that takes two parameters: the current node (node) and the result list. It checks if the current node is not null, and if so, it follows the inorder traversal order: left, root, right.
Approach 2: Iterative Solution Using a Stack
Another way to solve this problem is by using an iterative approach with a stack. Instead of recursion, we maintain a stack to keep track of the nodes that need to be processed.
Here’s the Java code for the iterative solution:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BinaryTreeInorderTraversal {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
}
}In this code, we use a stack to keep track of the nodes that need to be processed. We start with the root node and continue moving to the left child while pushing nodes onto the stack. When there are no more left children, we pop a node from the stack, add its value to the result list, and then move to its right child.
Testing the Solutions
To test our solutions, let’s create a binary tree and call the inorderTraversal method to get the inorder traversal of the tree. We’ll also print the result to verify that it matches our expectations.
public class Main {
public static void main(String[] args) {
// Create the binary tree
TreeNode root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
BinaryTreeInorderTraversal solution = new BinaryTreeInorderTraversal();
// Test the recursive solution
List<Integer> recursiveResult = solution.inorderTraversal(root);
System.out.println("Recursive Result: " + recursiveResult);
// Test the iterative solution
List<Integer> iterativeResult = solution.inorderTraversal(root);
System.out.println("Iterative Result: " + iterativeResult);
}
}When you run the code above, you should see the following output:
Recursive Result: [1, 3, 2]
Iterative Result: [1, 3, 2]Both solutions correctly produce the inorder traversal of the binary tree.
Complexity Analysis
Before we conclude, let’s briefly analyze the time and space complexity of our solutions.
Recursive Solution
- Time Complexity: O(n), where n is the number of nodes in the binary tree. This is because we visit each node once.
- Space Complexity: O(n) in the worst case due to the recursion stack, where n is the number of nodes.
Iterative Solution Using a Stack
- Time Complexity: O(n), where n is the number of nodes in the binary tree. Similar to the recursive solution, we visit each node once.
- Space Complexity: O(n) in the worst case due to the stack, where n is the number of nodes.
Conclusion
In this blog post, we explored the concept of binary tree inorder traversal, a fundamental technique for traversing binary trees. We also provided two solutions to the “Binary Tree Inorder Traversal” problem on LeetCode using Java. You learned how to implement the traversal recursively and iteratively using a stack. Both solutions correctly produced the inorder traversal of a binary tree.
Understanding binary tree traversal is essential not only for solving coding problems but also for real-world applications involving tree data structures. Whether you’re preparing for coding interviews or working on tree-related projects, these concepts and solutions will be valuable additions to your programming toolkit.
Thank You!
Read More –
Valid Palindrome and LeetCode Solution in Java: A Detailed Guide – https://kamleshsingad.com/valid-palindrome-and-leetcode-solution-in-java-a-detailed-guide/
118. Pascal’s Triangle | Pascal’s Triangle LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/118-pascals-triangle-pascals-triangle-leetcode-solution-in-java/
590. N-ary Tree Post order Traversal | n Array Tree Post Order Traversal LeetCode Solution in Java – https://kamleshsingad.com/590-n-ary-tree-post-order-traversal-n-array-tree-post-order-traversal/
