Binary Tree Preorder Traversal

                                            
/**
 * 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<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> s;
        if (root != nullptr) {
            s.push(root);
        }

        while (!s.empty()) {
            TreeNode* current = s.top();
            s.pop();
            result.push_back(current->val);
            if (current->right != nullptr) {
                s.push(current->right);
            }
            if (current->left != nullptr) {
                s.push(current->left);
            }
        }

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

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

void preorderHelper(struct TreeNode* node, int* result, int* returnSize){
    if(node == NULL) return;
    
    result[(*returnSize)++] = node->val;
    
    preorderHelper(node->left, result, returnSize);
    preorderHelper(node->right, result, returnSize);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = 0;
    int* result = (int*)malloc(100 * sizeof(int));
    
    preorderHelper(root, result, returnSize);
    
    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> PreorderTraversal(TreeNode root) {
        IList<int> result = new List<int>();
        if (root == null) return result;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            result.Add(node.val);
            
            if (node.right != null) {
                stack.Push(node.right);
            }
            if (node.left != null) {
                stack.Push(node.left);
            }
        }
        
        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)
 * }
 */
var preorderTraversal = function(root) {
    const result = [];
    const stack = [];
    let node = root;
    
    while (node || stack.length > 0) {
        while (node) {
            result.push(node.val);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.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 preorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    
    let current: TreeNode | null = root;
    
    while (current || stack.length > 0) {
        while (current) {
            result.push(current.val);
            stack.push(current);
            current = current.left;
        }
        
        const node = stack.pop()!;
        current = node.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 preorderTraversal(_ root: TreeNode?) -> [Int] {
        var result = [Int]()
        var stack = [TreeNode]()
        var node = root
        
        while !stack.isEmpty || node != nil {
            while node != nil {
                result.append(node!.val)
                stack.append(node!)
                node = node!.left
            }
            node = stack.removeLast().right
        }
        
        return result
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    stack := []*TreeNode{}
    result := []int{}
    
    for len(stack) > 0 || root != nil {
        for root != nil {
            result = append(result, root.Val)
            stack = append(stack, root)
            root = root.Left
        }
        
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        root = 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)
#         @val = val
#         @left, @right = left, right
#     end
# end

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

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

object Solution {
    def preorderTraversal(root: TreeNode): List[Int] = {
        if (root == null) return List()
        
        var result = List[Int]()
        var stack = List[TreeNode](root)
        
        while (stack.nonEmpty) {
            val node = stack.head
            stack = stack.tail
            result = node.value +: result
            
            if (node.right != null) stack = node.right +: stack
            if (node.left != null) stack = node.left +: stack
        }
        
        result.reverse
    }
}

                                            
%% Definition for a binary tree node.
%%
%% -record(tree_node, {val = 0 :: integer(),
%%                     left = null  :: 'null' | null,
%%                     right = null :: 'null' | null}).

preorder_traversal(null) -> [];
preorder_traversal({tree_node, Val, Left, Right}) ->
    [Val] ++ preorder_traversal(Left) ++ preorder_traversal(Right).

To solve this coding challenge, we need to perform a preorder traversal on a binary tree. In preorder traversal, we visit nodes in the following order: root, left subtree, and then right subtree. Let's break down both the recursive and iterative approaches.

# Explanation

Recursive Preorder Traversal:

Base Case : If the current node is
null

, return immediately.
Visit Node : Add the current node's value to the result list.
Left Subtree : Recursively perform preorder traversal on the left subtree.
Right Subtree : Recursively perform preorder traversal on the right subtree.

The recursive method is straightforward and more intuitive, but we need to convert it to an iterative solution that uses a stack since iterative solutions usually have better control over stack overflow issues in deeper trees.

Iterative Preorder Traversal:

Initialize Data Structures : Use a stack to keep track of nodes. This stack will help us simulate the recursion.
Traversal Process :

Push the root node onto the stack.
Loop until the stack is empty:

Pop the top node from the stack.
Visit the node by adding its value to the result list.
Push the right child to the stack (if exists).
Push the left child to the stack (if exists).

Detailed Steps in Pseudocode:

Initialize an empty list for the result to hold the node values.
Initialize a stack and push the root node onto it, if the root is not null.
While the stack is not empty:

Pop a node from the stack.
Add the node's value to the result list.
If the node has a right child, push the right child onto the stack.
If the node has a left child, push the left child onto the stack.

Return the result list once the stack is empty.

Pseudocode with Comments:

                                            
# This is the pseudocode for iterative preorder traversal for a binary tree

# Function: iterative_preorder_traversal
# Input: root (the root node of the binary tree)
# Output: result (a list containing the preorder traversal of node values)

function iterative_preorder_traversal(root):
    # Initialize an empty list to store the traversal result
    result = []
    
    # If the root is null, return the empty result list
    if root is null:
        return result
    
    # Initialize a stack to help with the traversal, starting with the root node
    stack = [root]
    
    # Loop until there are no nodes left in the stack
    while stack is not empty:
        # Pop the top node from the stack
        current_node = stack.pop()
        
        # Add the current node's value to the result list
        result.append(current_node.val)
        
        # If the current node has a right child, push it onto the stack
        if current_node.right is not null:
            stack.push(current_node.right)
        
        # If the current_node has a left child, push it onto the stack
        if current_node.left is not null:
            stack.push(current_node.left)
    
    # Return the filled result list after the traversal is complete
    return result

In this detailed explanation, the two critical points are crystal-clear: initialization of the data structure (the stack) and the order in which we process the nodes—this ensures that we correctly simulate the preorder traversal (root, left, right). By following this methodology, we ensure that our implementation of the preorder traversal on the binary tree is efficient, clear, and handles edge cases, such as empty trees.