Solution For Binary Tree Inorder Traversal
Problem Statement:
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Approach:
The inorder traversal of a binary tree is to traverse the left sub-tree, then visit the root, and finally traverse the right sub-tree. As we know that it’s a traverse of the tree, we can use Depth First Search (DFS) because it allows us to check the node in its left, right and current order, hence the inorder traversal’s requirement.
Algorithm:
- Define an empty list to store the inorder traversal.
- Define a function, say inorder_helper, that takes a node as input and performs the inorder traversal on its left, current, and right node following the required order.
- Check if the root node is not equal to Null, then perform the following steps:
a) Call the inorder_helper function recursively for the left child node passing its reference.
b) Append the current node’s value to the list.
c) Call the inorder_helper function recursively for the right child node passing its reference. - Finally, return the list of inorder traversal.
Pseudo Code:
“`
function inorder(root):
result = [] // Initialize empty list
inorder_helper(root, result) // Call inorder_helper() and pass root and result list
return result // return result list
function inorder_helper(current_node, result_list):
if current_node != null:
inorder_helper(current_node.left, result_list) // Recursive call for left child node
result_list.append(current_node.val) // Append current node’s value to the list
inorder_helper(current_node.right, result_list) // Recursive call for right child node
“`
Time Complexity:
Since we are visiting all the nodes of the tree, the time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.
Space Complexity:
For the auxiliary space, we are using a list to store the inorder traversal. The space occupied by the list is O(n), where n is the number of nodes in the binary tree.
Solution:
Python implementation of the above algorithm:
“`
Definition for a binary tree node.
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
result = [] # Initialize empty list
self.inorder_helper(root, result) # Call inorder_helper() and pass root and result list
return result # return result list
def inorder_helper(self, current_node, result_list):
if current_node is not None:
self.inorder_helper(current_node.left, result_list) # Recursive call for left child node
result_list.append(current_node.val) # Append current node's value to the list
self.inorder_helper(current_node.right, result_list) # Recursive call for right child node
“`
The above implementation passed all the test cases of the problem on LeetCode.
Step by Step Implementation For Binary Tree Inorder Traversal
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public ListinorderTraversal(TreeNode root) { List list = new ArrayList<>(); if(root == null) return list; Stack stack = new Stack<>(); TreeNode curr = root; while(curr != null || !stack.isEmpty()){ while(curr!= null){ stack.push(curr); curr = curr.left; } curr = stack.pop(); list.add(curr.val); curr = curr.right; } return list; } }
def inorderTraversal(root: TreeNode) -> List[int]: ans = [] # Base case if root == None: return ans # Recursive call on left subtree ans += inorderTraversal(root.left) # Add root to the answer ans.append(root.val) # Recursive call on right subtree ans += inorderTraversal(root.right) return ans
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function(root) { // create an empty array to store the results let results = []; // define a helper function const traverse = (node) => { // if the node exists, continue if (node) { // first recursively call traverse on the left node traverse(node.left); // push the value of the current node into results results.push(node.val); // finally recursively call traverse on the right node traverse(node.right); } } // start traversal from the root node traverse(root); // return the results array return results; };
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorinorderTraversal(TreeNode* root) { vector result; stack stk; TreeNode* cur = root; while(cur != nullptr || !stk.empty()){ while(cur != nullptr){ stk.push(cur); cur = cur->left; } cur = stk.top(); stk.pop(); result.push_back(cur->val); cur = cur->right; } return result; } };
public IListInorderTraversal(TreeNode root) { // create an empty stack and push root to it Stack stack = new Stack (); stack.Push(root); // create an empty output list List output = new List (); // while stack is not empty while (stack.Count > 0) { // pop the top item from stack TreeNode curr = stack.Pop(); // if current node is not null if (curr != null) { // push the left child of // current node to stack stack.Push(curr.left); // push the current node to stack stack.Push(curr); // push the right child of // current node to stack stack.Push(curr.right); } // if current node is null, we have // reached a leaf node else { // print the node and pop it off the stack output.Add(stack.Pop().val); } } // return the generated list return output; }