Binary Tree Inorder Traversal

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* curr = root;
        
        while (curr != NULL || !st.empty()) {
            while (curr != NULL) {
                st.push(curr);
                curr = curr->left;
            }
            
            curr = st.top();
            st.pop();
            res.push_back(curr->val);
            
            curr = curr->right;
        }
        
        return res;
    }
};

                                            
/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    int* result = (int*)malloc(100 * sizeof(int));
    int index = 0;
    
    struct TreeNode* stack[100];
    int top = -1;
    
    while (root != NULL || top != -1) {
        while (root != NULL) {
            stack[++top] = root;
            root = root->left;
        }
        root = stack[top--];
        result[index++] = root->val;
        root = root->right;
    }
    
    *returnSize = index;
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * 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>();

        while (root != null || stack.Count > 0) {
            while (root != null) {
                stack.Push(root);
                root = root.left;
            }

            root = stack.Pop();
            result.Add(root.val);
            root = root.right;
        }

        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 */

var inorderTraversal = function(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    
    return result;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current: TreeNode | null = root;
    
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        if (current) {
            result.push(current.val);
            current = current.right;
        }
    }
    
    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function inorderTraversal($root) {
        $result = [];
        $stack = [];
        $current = $root;
        
        while ($current !== null || !empty($stack)) {
            while ($current !== null) {
                array_push($stack, $current);
                $current = $current->left;
            }
            $current = array_pop($stack);
            $result[] = $current->val;
            $current = $current->right;
        }
        
        return $result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

class Solution {
    fun inorderTraversal(root: TreeNode?): List<Int> {
        val res = mutableListOf<Int>()
        val stack = Stack<TreeNode>()
        var curr = root

        while (curr != null || stack.isNotEmpty()) {
            while (curr != null) {
                stack.push(curr)
                curr = curr.left
            }
            curr = stack.pop()
            res.add(curr.`val`)
            curr = curr.right
        }
        
        return res
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    var res []int
    var stack []*TreeNode
    curr := root
    for curr != nil || len(stack) > 0 {
        for curr != nil {
            stack = append(stack, curr)
            curr = curr.Left
        }
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, node.Val)
        curr = node.Right
    }
    return res
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#     end
# end

def inorder_traversal(root)
    result = []
    stack = []
    current = root
    
    while current || !stack.empty?
        while current
            stack.push(current)
            current = current.left
        end
        
        current = stack.pop
        result.push(current.val)
        current = current.right
    end
    
    return result
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *     var value: Int = _value
 *     var left: TreeNode = _left
 *     var right: TreeNode = _right
 * }
 */
object Solution {
    def inorderTraversal(root: TreeNode): List[Int] = {
        var res = List[Int]()
        def inorder(node: TreeNode): Unit = {
            if (node == null) return
            inorder(node.left)
            res = res :+ node.value
            inorder(node.right)
        }
        inorder(root)
        res
    }
}

                                            
%% Definition for a binary tree node.
%%
%% -record(tree_node, {val = 0 :: integer(),
%%                     left = null  :: 'null' | 
inorder_traversal(null) ->
    [];
inorder_traversal(#tree_node{left = Left, val = Val, right = Right}) ->
    inorder_traversal(Left) ++ [Val] ++ inorder_traversal(Right).

To solve this coding challenge, we need to perform an inorder traversal of a binary tree. Inorder traversal is a depth-first search strategy where the nodes are traversed in the following order: left subtree, the root node, and then the right subtree. This challenge can be solved using both recursive and iterative approaches, but we will focus on the iterative approach based on the details provided in the example solution.

# Explanation

In Binary Tree Inorder Traversal, we traverse the binary tree in an orderly fashion, left node first, the root node second, and the right node last. The primary use of this traversal method is when you need to visit the nodes in a non-decreasing order.

Step-by-Step Explanation:

1. Understanding Binary Tree Structure A binary tree node typically consists of a value and pointers to its left and right child nodes. We'll assume the binary tree is represented by a root node. 2. Inorder Traversal Using a Stack To achieve inorder traversal iteratively, we will use a Stack. The general idea is to traverse to the leftmost node first, then visit the node itself, and finally explore the right subtree. Here are the steps broken down:

Initialize an empty stack and a list to store the result.
Start from the root node and traverse left while pushing nodes onto the stack.
Once a null node is reached, pop a node from the stack. This node is visited next.
Add the node's value to the result list.
Move to the node's right child and repeat steps 2-5.

Detailed Steps in Pseudocode:

                                            
# Step 1: Initialization
Initialize an empty list named result to store the values of nodes.
Initialize an empty stack to help with the traversal.
Set the current node to the root node of the tree.

# Step 2: Traverse the Tree
while current is not None or stack is not empty:
    # Traverse left subtree
    while current is not None:
        Push the current node onto the stack.
        Move to the left child of the current node.
    
    # Visit the node
    Pop the node from the top of the stack.
    Add the value of this node to the result list.
    
    # Traverse right subtree
    Move to the right child of the node.

# Step 3: Return the result list
Return result

# Explanation With Pseudocode:

Let's translate this step-by-step logic into more detailed pseudocode including comments:

                                            
# Initialize an empty list to store the inorder traversal result
result = []

# Initialize an empty stack to keep track of nodes
stack = []

# Set the current node to the root
current = root

# Continue traversing until all nodes are processed
while current is not None or stack is not empty:
    
    # Traverse to the leftmost child
    while current is not None:
        # Push the current node onto the stack
        stack.append(current)
        # Move to the left child of the current node
        current = current.left
    
    # Pop a node from the stack (Inorder visitation)
    current = stack.pop()
    
    # Add the node's value to the result list
    result.append(current.val)
    
    # Now, explore the right subtree (if any)
    current = current.right

# Return the resultant inorder traversal
return result

Combining All Together

Final Pseudocode for Iterative Inorder Traversal:

                                            
# Initialize an empty list to store the inorder traversal result
result = []

# Initialize an empty stack to keep track of nodes
stack = []

# Set the current node to the root
current = root

# Continue traversing until all nodes are processed
while current is not None or stack is not empty:
    
    # Traverse to the leftmost child
    while current is not None:
        # Push the current node onto the stack
        stack.append(current)
        # Move to the left child of the current node
        current = current.left
    
    # Pop a node from the stack (Inorder visitation)
    current = stack.pop()
    
    # Add the node's value to the result list
    result.append(current.val)
    
    # Now, explore the right subtree (if any)
    current = current.right

# Return the resultant inorder traversal
return result

By implementing the pseudocode provided, you can perform an inorder traversal iteratively on any given binary tree. This approach ensures that the nodes are visited in the correct order and efficiently utilizes the stack data structure to manage the traversal.