Tech World Software SchoolTWSS

LeetCode problem#257

Binary Tree Paths

Solved in 1 languageJava

Solve it on LeetCode(opens in a new tab)

Solution

40 lines
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    private void traverse(TreeNode root, String pathSoFar, List<String> list) {
18        if (root == null) {
19            return;
20        }
21
22        if (pathSoFar.length() > 0) {
23            pathSoFar = pathSoFar + "->";
24        }
25        pathSoFar = pathSoFar + root.val;
26
27        if (root.left == null && root.right == null) {
28            // a leaf
29            list.add(pathSoFar);
30        }
31
32        traverse(root.left, pathSoFar, list);
33        traverse(root.right, pathSoFar, list);
34    }
35    public List<String> binaryTreePaths(TreeNode root) {
36        List<String> list = new LinkedList<String>();
37        traverse(root, "", list);
38        return list;
39    }
40}

How it works

This LeetCode problem solution is aimed at finding all the root-to-leaf paths in a binary tree and returning them as a list of strings. Let's break down the solution step by step:

Problem Understanding

Given a binary tree, we want to return all paths from the root node to the leaf nodes. A path is represented by concatenating the values of nodes along the path, separated by "->".

Class Structure

  1. TreeNode: The TreeNode class defines the structure of a node in the binary tree. Each node has:

    • An integer value (val)
    • A reference to its left child (left)
    • A reference to its right child (right)

  2. Solution: The Solution class contains the method used to find the paths.

Method Breakdown

binaryTreePaths(TreeNode root)

  • This is the entry point for the solution.
  • It initializes a list (list) which will store the resulting paths.
  • It calls the helper method traverse with the root of the tree, an empty string for the current path (pathSoFar), and the list to collect paths.

traverse(TreeNode root, String pathSoFar, List<String> list)

This method performs a recursive depth-first traversal of the binary tree. Here's how it works:

  1. Base Case: If the current node root is null, it means we've reached the end of a branch (i.e., a non-existent node), and we simply return, doing nothing further.

  2. Building the Path:

    • If pathSoFar is non-empty, it appends "->" to pathSoFar, which separates the values in the path.
    • Then it appends the value of the current node (root.val) to pathSoFar.

  3. Leaf Node Check:

    • A node is considered a leaf node if both root.left and root.right are null, meaning it does not have any children.
    • If the current node is a leaf, it adds the constructed pathSoFar to the list.

  4. Recursive Calls:

    • The method then recursively calls itself for the left child of the current node (traverse(root.left, pathSoFar, list)).
    • After that, it calls itself for the right child (traverse(root.right, pathSoFar, list)).

Summary

The algorithm uses depth-first search (DFS) to explore all paths from the root to the leaves. It employs recursion to build paths as it descends into the tree, and upon reaching a leaf, it saves that path into the resulting list.

Time Complexity

The time complexity of the solution is O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity

The space complexity is O(H + L), where H is the height of the binary tree (due to the recursion stack) and L is the total length of all paths stored in the list. In the worst case of a completely unbalanced tree, this can approach O(N).

Overall, this solution nicely demonstrates how recursion can be used for tree traversal to collect paths, which is a common interview question in algorithms and data structures.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.