Binary Tree Paths

                                            
/**
 * 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<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if (root == nullptr) {
            return paths;
        }
        binaryTreePathsDFS(root, "", paths);
        return paths;
    }
    
    void binaryTreePathsDFS(TreeNode* node, string path, vector<string>& paths) {
        if (node->left == nullptr && node->right == nullptr) {
            paths.push_back(path + to_string(node->val));
            return;
        }
        if (node->left != nullptr) {
            binaryTreePathsDFS(node->left, path + to_string(node->val) + "->", paths);
        }
        if (node->right != nullptr) {
            binaryTreePathsDFS(node->right, path + to_string(node->val) + "->", paths);
        }
    }
};

                                            
import java.util.List;
import java.util.ArrayList;

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root != null) {
            dfs(root, "", paths);
        }
        return paths;
    }
    
    private void dfs(TreeNode node, String path, List<String> paths) {
        if (node.left == null && node.right == null) {
            paths.add(path + node.val);
            return;
        } 
        
        if (node.left != null) {
            dfs(node.left, path + node.val + "->", paths);
        }
        
        if (node.right != null) {
            dfs(node.right, path + node.val + "->", paths);
        }
    }
}

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

void binaryTreePathsHelper(struct TreeNode* node, char* path, int pathLen, char** result, int* returnSize) {
    if (node == NULL) {
        return;
    }
    
    pathLen += sprintf(path + pathLen, "%d", node->val);
    
    if (node->left == NULL && node->right == NULL) {
        path[pathLen] = '\0';
        result[(*returnSize)++] = strdup(path);
        return;
    } else {
        pathLen += sprintf(path + pathLen, "->");
        binaryTreePathsHelper(node->left, path, pathLen, result, returnSize);
        binaryTreePathsHelper(node->right, path, pathLen, result, returnSize);
    }
}

char **binaryTreePaths(struct TreeNode* root, int* returnSize) {
    char* path = (char*)malloc(1000*sizeof(char)); // Max length assumed
    char** result = (char**)malloc(1000*sizeof(char*));
    *returnSize = 0;
    binaryTreePathsHelper(root, path, 0, result, returnSize);
    free(path);
    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<string> BinaryTreePaths(TreeNode root) {
        IList<string> paths = new List<string>();
        if(root == null) return paths;
        
        TraverseTree(root, "", paths);
        return paths;
    }
    
    private void TraverseTree(TreeNode node, string pathSoFar, IList<string> paths) {
        if(node == null) return;
        
        pathSoFar += node.val.ToString();
        
        if(node.left == null && node.right == null) {
            paths.Add(pathSoFar);
        } else {
            pathSoFar += "->";
            TraverseTree(node.left, pathSoFar, paths);
            TraverseTree(node.right, pathSoFar, paths);
        }
    }
}

                                            
const binaryTreePaths = function(root) {
    const paths = [];
    
    const constructPaths = function(node, path) {
        if (node) {
            path += node.val.toString();
            if (node.left === null && node.right === null) {
                paths.push(path);
            } else {
                path += '->';
                constructPaths(node.left, path);
                constructPaths(node.right, path);
            }
        }
    };
    
    constructPaths(root, '');
    
    return paths;
};

                                            
/**
 * 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 binaryTreePaths(root: TreeNode | null): string[] {
    const paths: string[] = [];
    
    const buildPath = (node: TreeNode, path: string) => {
        if (!node) return;
        
        path += node.val.toString();
        if (!node.left && !node.right) {
            paths.push(path);
        } else {
            path += '->';
            buildPath(node.left, path);
            buildPath(node.right, path);
        }
    }
    
    buildPath(root, '');
    return paths;
}

                                            
/**
 * 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 String[]
     */
    function binaryTreePaths($root) {
        $paths = [];
        $this->dfs($root, "", $paths);
        return $paths;
    }
    
    function dfs($node, $path, &$paths) {
        if ($node) {
            $path .= $node->val;
            if (!$node->left && !$node->right) {
                $paths[] = $path;
            } else {
                $path .= "->";
                $this->dfs($node->left, $path, $paths);
                $this->dfs($node->right, $path, $paths);
            }
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun binaryTreePaths(root: TreeNode?): List<String> {
        val paths = mutableListOf<String>()
        if (root == null) {
            return paths
        }
        dfs(root, "", paths)
        return paths
    }
    
    private fun dfs(node: TreeNode, path: String, paths: MutableList<String>) {
        if (node.left == null && node.right == null) {
            paths.add(path + node.`val`)
            return
        }
        if (node.left != null) {
            dfs(node.left!!, "$path${node.`val`}->", paths)
        }
        if (node.right != null) {
            dfs(node.right!!, "$path${node.`val`}->", paths)
        }
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func binaryTreePaths(root *TreeNode) []string {
    var paths []string
    if root == nil {
        return paths
    }
    
    var dfs func(node *TreeNode, path string)
    dfs = func(node *TreeNode, path string) {
        if node == nil {
            return
        }
        path += strconv.Itoa(node.Val)
        if node.Left == nil && node.Right == nil {
            paths = append(paths, path)
        } else {
            path += "->"
            dfs(node.Left, path)
            dfs(node.Right, path)
        }
    }
    
    dfs(root, "")
    
    return paths
}

                                            
class TreeNode
    attr_accessor :val, :left, :right
    def initialize(val = 0, left = nil, right = nil)
        @val = val
        @left = left
        @right = right
    end
end

def binary_tree_paths(root)
    paths = []
    
    def dfs(node, path, paths)
        return if node.nil?
        
        path += "#{node.val}"
        
        if node.left.nil? && node.right.nil?
            paths << path
        else
            path += "->"
            dfs(node.left, path, paths)
            dfs(node.right, path, paths)
        end
    end
    
    dfs(root, "", paths)
    return paths
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 binaryTreePaths(root: TreeNode): List[String] = {
        def paths(node: TreeNode, path: String): List[String] = {
            if (node == null) {
                List()
            } else if (node.left == null && node.right == null) {
                List(path + node.value)
            } else {
                paths(node.left, path + node.value + "->") ::: paths(node.right, path + node.value + "->")
            }
        }
        
        paths(root, "").toList
    }
}

To solve this coding challenge, you need to traverse the binary tree and record all the unique root-to-leaf paths. Each path should be represented using the node values connected by '->'. Such a traversal ensuring to capture all root-to-leaf paths can be done using depth-first search (DFS) due to its natural traversal of every path from the root to the leaves.

Explanation

Given the root of a binary tree, we need to find and return all the paths from the root to each leaf node. A leaf node is defined as a node that has no children (both its left and right child pointers are null). We'll use a depth-first search (DFS) strategy to explore each possible path from the root to the leaves. At each node, we add the node's value to the current path representation. If we reach a leaf node, we'll finalize the path and add it to the list of paths. If the node is not a leaf, we continue the DFS on its children (left and right). Detailed steps:

Initialization - Create a list to store all root-to-leaf paths.
DFS Implementation :

Start the DFS from the root node.
Add the current node's value to the path.
If the node is a leaf, add the path to the list of paths.
If not, recursively call DFS on the left and right children.

Termination - Return the list of paths once DFS completes.

This ensures we capture all possible paths from the root to the leaves in the required format.

Step-by-Step Explanation/Detailed Steps in Pseudocode

                                            
# Define the function which receives the root of the binary tree
Function binaryTreePaths(root):
    # Initialize an empty list to store paths
    paths = []

    # Define inner function to perform depth-first search (DFS)
    Function constructPaths(node, path):
        # Check if the current node is not null
        If node is not null:

            # Add the value of the current node to the path
            path += node.value.toString()

            # Check if the current node is a leaf node
            If node.left is null and node.right is null:
                # It's a leaf node, add the current path to paths list
                paths.add(path)
            Else:
                # It's not a leaf node, continue exploring its children
                # Add separator '->' to the current path
                path += '->'

                # Recursively call DFS on the left child
                constructPaths(node.left, path)

                # Recursively call DFS on the right child
                constructPaths(node.right, path)

    # Initial call to DFS with the root node and an empty path string
    constructPaths(root, '')

    # Return the list of all root-to-leaf paths found
    Return paths

# Example to illustrate the traversal and path capturing
# Input: [1, 2, 3, null, 5]
# Expected Output: ["1->2->5", "1->3"]

# When the function binaryTreePaths is called with the root node of the tree:
# - It starts at the root node (1) with an empty path.
# - Then it moves to the left child (2) and adds '1->' to the path.
# - From node (2), it tries to move to its left child which is null (does nothing).
# - Then it moves to the right child (5) and completes the path '1->2->5'.
# - Since node (5) is a leaf, it adds the path to paths.
# - It backtracks and explores the right child of node (1) which is (3).
# - It completes the path '1->3' and adds it to paths since node (3) is a leaf.
# - Finally, the function returns the list of paths ["1->2->5", "1->3"].

In summary, we use a DFS approach to explore each possible path from the root to the leaves, and at each leaf node, we add the completed path to our list of paths. The process ensures all root-to-leaf paths are captured and returned in the specified format.