Binary Tree Postorder 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> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == NULL)
            return result;
        
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* curr = st.top();
            st.pop();
            result.insert(result.begin(), curr->val);
            if(curr->left)
                st.push(curr->left);
            if(curr->right)
                st.push(curr->right);
        }
        
        return result;
    }
};

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

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* postorderTraversal(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 = 0;
    struct TreeNode* prev = NULL;
    
    while(root != NULL || top > 0){
        while(root != NULL){
            stack[top++] = root;
            root = root->left;
        }
        
        struct TreeNode* temp = stack[top - 1];
        
        if(temp->right == NULL || temp->right == prev){
            result[index++] = temp->val;
            top--;
            prev = temp;
        }else{
            root = temp->right;
        }
    }
    
    *returnSize = index;
    return result;
}

                                            
public class Solution {
    public IList<int> PostorderTraversal(TreeNode root) {
        IList<int> result = new List<int>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack1 = new Stack<TreeNode>();
        Stack<TreeNode> stack2 = new Stack<TreeNode>();
        stack1.Push(root);

        while (stack1.Count > 0) {
            TreeNode node = stack1.Pop();
            stack2.Push(node);

            if (node.left != null) {
                stack1.Push(node.left);
            }

            if (node.right != null) {
                stack1.Push(node.right);
            }
        }

        while (stack2.Count > 0) {
            result.Add(stack2.Pop().val);
        }

        return result;
    }
}

                                            
/**
 * 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 postorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let curr = root;
    let prev = null;
    
    while (curr || stack.length > 0) {
        if (curr) {
            stack.push(curr);
            curr = curr.left;
        } else {
            let peekNode = stack[stack.length - 1];
            if (peekNode.right && peekNode.right !== prev) {
                curr = peekNode.right;
            } else {
                res.push(peekNode.val);
                prev = stack.pop();
            }
        }
    }
    
    return res;
};

                                            
/**
 * 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 postorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current = root;
    let lastVisited = null;
    
    while (current || stack.length > 0) {
        if (current) {
            stack.push(current);
            current = current.left;
        } else {
            const peek = stack[stack.length - 1];
            if (peek.right && peek.right !== lastVisited) {
                current = peek.right;
            } else {
                result.push(peek.val);
                lastVisited = stack.pop();
            }
        }
    }
    
    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 postorderTraversal($root) {
        $result = [];
        $stack = new SplStack();
        $prev = null;

        while (!empty($stack) || $root != null) {
            while ($root != null) {
                $stack[] = $root;
                $root = $root->left;
            }
            $root = $stack->isEmpty() ? null : $stack->top(); // Check if the stack is empty before accessing top
            if ($root == null) {
                break; // Handle null case
            }
            if ($root->right == null || $root->right == $prev) {
                $result[] = $root->val;
                $prev = $root;
                $stack->pop();
                $root = null;
            } else {
                $root = $root->right;
            }
        }

        return $result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        var stack = [TreeNode]()
        var currentNode = root
        var lastVisited: TreeNode? = nil
        
        while currentNode != nil || !stack.isEmpty {
            if currentNode != nil {
                stack.append(currentNode!)
                currentNode = currentNode!.left
            } else {
                let peekNode = stack[stack.count - 1]
                if peekNode.right != nil && lastVisited !== peekNode.right {
                    currentNode = peekNode.right
                } else {
                    result.append(peekNode.val)
                    lastVisited = stack.removeLast()
                }
            }
        }
        
        return result
    }
}

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

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

def postorder_traversal(root)
    result = []
    stack = []
    return result if root.nil?
    
    stack << root
    while !stack.empty?
        node = stack.pop
        result.unshift(node.val)
        stack << node.left if node.left
        stack << node.right if node.right
    end
    
    result
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode 
= null, _right: TreeNode = null) {
 *   def value: Int = _value
 *   def left: TreeNode = _left
 *   def right: TreeNode = _right
 * }
 */

object Solution {
  def postorderTraversal(root: TreeNode): List[Int] = {
    def doPostorder(node: TreeNode, acc: List[Int]): List[Int] = {
      if (node == null) {
        acc
      } else {
        doPostorder(node.left, doPostorder(node.right, node.value :: acc))
      }
    }
    doPostorder(root, List())
  }
}

                                            
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }

use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = Vec::new();
        let mut stack = Vec::new();
        
        if let Some(node) = root {
            stack.push(node);
        }
        
        while let Some(curr) = stack.pop() {
            let curr_borrow = curr.borrow();
            result.push(curr_borrow.val);
            
            if let Some(left) = &curr_borrow.left {
                stack.push(left.clone());
            }

            if let Some(right) = &curr_borrow.right {
                stack.push(right.clone());
            }
        }
        
        result.reverse();
        result
    }
}

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

To solve this coding challenge, we need to perform a postorder traversal of a binary tree. In postorder traversal, we visit the left subtree first, then the right subtree, and finally the root node. Given the constraints and the detailed requirements, we will discuss both the recursive and iterative solutions for this problem. The follow-up requirement urges us to solve this using an iterative approach.

Explanation

Postorder traversal of a binary tree requires visiting the left child, then the right child, and then the node itself. This is different from inorder or preorder traversals where the node itself is visited before either of its children. Let's first outline the recursive approach, which is straightforward but less efficient for deep trees because of the stack depth.

Recursive Approach:

If the node is
None

, return an empty list.
Recursively traverse the left subtree and store the result.
Recursively traverse the right subtree and store the result.
Finally, add the node's value to the result list.
Concatenate all the results and return.

Iterative Approach:

To avoid recursion and use an iterative method, we can use a stack to simulate the call stack behavior:

Initialize stack with the root node (if it exists).
Use a loop to process nodes:

Push left children to the stack.
Once no more left children, peek the stack and check its right child.
If the right child exists and has not been processed yet, process the right child.
If there's no right child or it has already been processed, process the node itself (add its value to the result and mark it as processed).

Repeat until the stack is empty.

We also track the previously visited node to ensure we do not revisit nodes.

Detailed Steps in Pseudocode:

Initialization :

Create a stack to keep track of nodes.
Initialize
current_node

to the root of the tree.
Initialize
previous_node

to
None

to keep track of the previously processed node.
Initialize an empty list
result

to store the traversal output.

                                            
stack = []
current_node = root
previous_node = None
result = []

Traversal :

While
current_node

is not
None

or
stack

is not empty:

                                            
while current_node is not None or stack is not empty:

Push Left Subtree :

Traverse the left subtree first by pushing all left children onto the stack.

                                            
if current_node is not None:
stack.append(current_node)
current_node = current_node.left

Backtrack :

If current_node is
None

, backtrack and process the right subtree.

                                            
else:
peek_node = stack[-1]  # Peek the top of the stack
if peek_node.right is not None and previous_node is not peek_node.right:
current_node = peek_node.right
else:
result.append(peek_node.value)
previous_node = stack.pop()
current_node = None

This algorithm ensures we visit each node exactly once and keeps track of the previously visited node to manage the traversal correctly.

Pseudocode with Comments:

                                            
# Initialize the stack to keep track of nodes
stack = []

# Start with the root node
current_node = root

# This variable keeps track of the previously processed node
previous_node = None

# List to store the result of postorder traversal
result = []

# Continue until there are nodes to be processed
while current_node is not None or not empty(stack):
    
    # Traverse the left subtree by pushing all left children to the stack
    if current_node is not None:
        stack.push(current_node)
        current_node = current_node.left
    
    else:
        # Peek the last node from the stack
        peek_node = top(stack)
        
        # Traverse the right subtree if it exists and is not processed
        if peek_node.right is not None and previous_node is not peek_node.right:
            current_node = peek_node.right
        
        else:
            # Process the node by adding to result and mark it as processed
            result.append(peek_node.value)
            previous_node = stack.pop()
            current_node = None

# Return the result of the postorder traversal
return result

This detailed explanation and pseudocode should provide a clear understanding of how to implement both the recursive and iterative solutions for the binary tree postorder traversal problem. Make sure to test the iterative pseudocode with different binary tree configurations to validate its correctness thoroughly.