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:

1. Define an empty list to store the inorder traversal.
2. 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.
3. 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.
4. 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 List inorderTraversal(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:
    vector inorderTraversal(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 IList InorderTraversal(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; }