700135. Inorder Traversal
Inorder Traversal
Slug: inorder-traversal
Difficulty: Easy
Id: 700135
Topic Tags: Tree, Data Structures
Company Tags: Amazon, Snapdeal, Adobe
Summary
In this problem, we are asked to perform an inorder traversal on a given binary tree. Inorder traversal is a type of tree traversal that visits the nodes in ascending order. It starts at the leftmost node and goes right, visiting all nodes before moving up the tree.
Detailed Explanation
The algorithm for inorder traversal involves recursively traversing the left subtree, visiting the current node, and then recursively traversing the right subtree. Here's a step-by-step breakdown of the solution:
- Start by defining a function that performs the inorder traversal.
- In the function, first traverse the left subtree (if it exists).
- Visit the current node (i.e., print its value or perform some other operation).
- Traverse the right subtree (if it exists).
- Repeat steps 2-4 for each node in the tree.
Here's an ASCII art diagram to illustrate the process:
1
/ \
2 3
/ \ /
4 5 6
Inorder traversal would visit the nodes in this order: 4, 2, 5, 1, 3, 6.
Time complexity for this algorithm is O(n), where n is the number of nodes in the tree. This is because we need to visit each node once. Space complexity is O(h), where h is the height of the tree. This is because the maximum depth of recursion call stack can go up to the height of the tree.
Optimized Solutions
Java
public void inorderTraversal(Node node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.println(node.val);
inorderTraversal(node.right);
}