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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def inorderTraversal(self, root):
9 result = []
10 self.inorder(root, result)
11 return result
12
13 def inorder(self, root, result):
14 if root is not None:
15 self.inorder(root.left, result)
16 result.append(root.val)
17 self.inorder(root.right, result)The Python solution uses a class-based approach with two methods. The inorderTraversal method initializes the result list and invokes a recursive inorder method to populate the list with the node values following an inorder sequence.
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
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<int> InorderTraversal(TreeNode root) {
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || stack.Count > 0) {
while (current != null) {
stack.Push(current);
current = current.left;
}
current = stack.Pop();
result.Add(current.val);
current = current.right;
}
return result;
}
}In C#, the iterative approach uses the .NET Stack class to iterate over the tree nodes in an inorder fashion. This stack management is critical for maintaining state between node processing.