HomeLeetcode257. Binary Tree Paths - Leetcode Solutions
Leetcode

257. Binary Tree Paths – Leetcode Solutions

Declan Clarke

Description

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Examples:

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

Solution in Python

To solve this problem in Python, we will traverse the binary tree starting from the root node and find all root-to-leaf paths. A leaf is defined as a node with no children (i.e., both its left and right children are None). We will use Depth-First Search (DFS) to explore each path from the root to the leaves, and during the traversal, we’ll maintain the current path and append it to the result list once we reach a leaf node.

Approach:

  1. DFS Traversal:
    • We perform a DFS from the root, keeping track of the path from the root to the current node.
    • If the current node is a leaf (i.e., it has no left or right child), we add the path to the result list.
    • If the current node is not a leaf, we continue traversing its left and right children.
  2. Path Formation:
    • We will build the path as a string where the node values are connected with "->".
    • For each recursive call, we append the current node’s value to the path.
  3. Base Case:
    • If the root is None, we simply return an empty list since there are no paths.
Python
class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        # Initialize an empty list to store the paths
        result = []
        
        # Helper function to perform DFS traversal
        def dfs(node, path):
            if not node:
                return  # If the node is None, simply return
            
            # Append the current node's value to the path
            path += str(node.val)
            
            # Check if the current node is a leaf node
            if not node.left and not node.right:
                # If it's a leaf, add the current path to the result list
                result.append(path)
            else:
                # If it's not a leaf, continue to traverse the left and right children
                path += "->"  # Add the '->' separator to continue building the path
                if node.left:
                    dfs(node.left, path)  # Recursive call for the left child
                if node.right:
                    dfs(node.right, path)  # Recursive call for the right child
        
        # Start DFS traversal from the root with an empty path
        dfs(root, "")
        
        # Return the list of all root-to-leaf paths
        return result

Detailed Explanation:

  1. Helper Function (dfs):
    • The helper function dfs takes two arguments:
      • node: the current node being processed.
      • path: the current path from the root to this node, represented as a string.
    • If the current node is None, we return since there’s nothing to process.
    • If the current node is a leaf (i.e., both node.left and node.right are None), the current path is complete, and we add it to the result list.
    • If the current node is not a leaf, we add the "->" separator to the path and continue the DFS on the left and right children (if they exist).
  2. Base Case:
    • The function dfs stops when it encounters a None node, i.e., when a branch of the tree ends.
    • If the root is None, the result will remain empty, and we return an empty list.
  3. Recursive Traversal:
    • Starting from the root, we build the path by recursively visiting each node’s left and right child.
    • Whenever a leaf node is reached, the constructed path string is appended to the result.
  4. Edge Cases:
    • Single Node Tree: If the tree consists of only one node, the path will simply be the value of that node.
    • Empty Tree: If the root is None, we return an empty list because there are no paths.

Solution in C++

C++
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;  // This will store all the root-to-leaf paths
        
        // Helper function to perform DFS traversal and build paths
        if (root) {
            dfs(root, "", result);  // Start DFS with an empty path
        }
        
        return result;
    }
    
    // Helper function to perform DFS and build paths
    void dfs(TreeNode* node, string path, vector<string>& result) {
        // Add the current node's value to the path
        path += to_string(node->val);
        
        // Check if it's a leaf node (both children are nullptr)
        if (!node->left && !node->right) {
            // If it is a leaf, add the current path to the result
            result.push_back(path);
        } else {
            // If it's not a leaf, continue building the path
            path += "->";  // Append '->' to indicate the path continues
            
            // Recursively call dfs for the left and right children
            if (node->left) {
                dfs(node->left, path, result);  // Explore the left child
            }
            if (node->right) {
                dfs(node->right, path, result);  // Explore the right child
            }
        }
    }
};

Solution in Javascript

JavaScript
var binaryTreePaths = function(root) {
    // This array will store all the root-to-leaf paths
    let paths = [];

    // Helper function for Depth-First Search (DFS) traversal
    function dfs(node, currentPath) {
        // If node is null, just return (base case)
        if (!node) return;

        // Append the current node's value to the path string
        currentPath += node.val;

        // If the current node is a leaf (both children are null)
        if (!node.left && !node.right) {
            // Add the completed path to the paths array
            paths.push(currentPath);
        } else {
            // If the node is not a leaf, continue the path with "->"
            currentPath += "->";

            // Recursively call dfs on the left and right children
            if (node.left) {
                dfs(node.left, currentPath);
            }
            if (node.right) {
                dfs(node.right, currentPath);
            }
        }
    }

    // Start DFS traversal from the root node with an empty path
    if (root) {
        dfs(root, "");
    }

    // Return the array of all root-to-leaf paths
    return paths;
};

Solution in Java

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

class Solution {
    
    // Function to return all root-to-leaf paths
    public List<String> binaryTreePaths(TreeNode root) {
        // List to store the result paths
        List<String> paths = new ArrayList<>();
        
        // If the root is null, return the empty paths list
        if (root == null) {
            return paths;
        }

        // Call the recursive helper function to start the DFS traversal
        dfs(root, "", paths);
        
        // Return the list of all paths
        return paths;
    }

    // Helper function to perform depth-first search (DFS) on the tree
    private void dfs(TreeNode node, String currentPath, List<String> paths) {
        // If the node is null, return (base case)
        if (node == null) {
            return;
        }

        // Append the current node's value to the path
        currentPath += Integer.toString(node.val);

        // Check if the current node is a leaf (no left or right children)
        if (node.left == null && node.right == null) {
            // If it is a leaf, add the complete path to the result list
            paths.add(currentPath);
        } else {
            // If not a leaf, continue the path with "->" and recursively call for left and right children
            currentPath += "->";
            dfs(node.left, currentPath, paths); // Traverse the left subtree
            dfs(node.right, currentPath, paths); // Traverse the right subtree
        }
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com