Given a binary tree, return all root-to-leaf paths.

Given a binary tree, return all root-to-leaf paths. A leaf is a node with no children.

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Recursive Solution:

class Solution {
    List<String> paths = null;

    public List<String> binaryTreePathsRecursive(TreeNode root) {
        paths = new ArrayList<>();
        constructPath(root, "");
        return paths;
    }

    private void constructPath(TreeNode node, String path) {
        if (node == null) return;
        path += node.val;
        if (node.left == null && node.right == null) {
            paths.add(path);
        } else {
            path += "->";
            constructPath(node.left, path);
            constructPath(node.right, path);
        }
    }
}

Time complexity: We visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes.

Space complexity: O(N). Here we use the space for a stack call and for a paths list to store the answer.  paths contains as many elements as leaves in the tree and hence couldn’t be larger than logN for the trees containing more than one element. Hence the space complexity is determined by a stack call. In the worst case, when the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be O(N). But in the best case (the tree is balanced), the height of the tree would be logN. Therefore, the space complexity, in this case, would be O(log(N)).

Iterative Solution Using Stack:

class Solution {
    public List<String> binaryTreePaths_1(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        LinkedList<TreeNode> nodeStack = new LinkedList<>();
        LinkedList<String> pathStack = new LinkedList<>();
        nodeStack.add(root);
        pathStack.add(String.valueOf(root.val));
        String path = null;
        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.removeLast();
            path = pathStack.removeLast();
            if (node.left == null && node.right == null) {
                paths.add(path);
            }
            if (node.left != null) {
                nodeStack.add(node.left);
                pathStack.add(path + "->" + String.valueOf(node.left.val));
            }
            if (node.right != null) {
                nodeStack.add(node.right);
                pathStack.add(path + "->" + String.valueOf(node.right.val));
            }
        }
        return paths;
    }
}

Iterative Solution Using Queue:

class Solution {
    public List<String> binaryTreePaths_2(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<String> pathQueue = new LinkedList<>();
        nodeQueue.add(root);
        pathQueue.add(String.valueOf(root.val));
        String path = null;
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            path = pathQueue.poll();
            if (node.left == null && node.right == null) {
                paths.add(path);
            }
            if (node.left != null) {
                nodeQueue.add(node.left);
                pathQueue.add(path + "->" + String.valueOf(node.left.val));
            }
            if (node.right != null) {
                nodeQueue.add(node.right);
                pathQueue.add(path + "->" + String.valueOf(node.right.val));
            }
        }
        return paths;
    }
}
  • Time complexity: O(N) since each node is visited exactly once.
  • Space complexity: O(N) as we could keep up to the entire tree.

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s