algoadvance

Leetcode 257. Binary Tree Paths

Problem Statement

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

A leaf is a node with no children.

Clarifying Questions

  1. What is the definition of a leaf node? A leaf node is a node that has no left or right child.

  2. What should the output look like? The output should be a list of strings where each string represents a path from the root to a leaf node.

  3. Are there any constraints on the tree?

    • The number of nodes in the tree is in the range [1, 100].
    • The tree is a binary tree, meaning each node has at most two children.
    • The value of each node is between -100 and 100.

Strategy

  1. Depth-First Search (DFS) Traversal:
    • Perform a DFS traversal of the binary tree.
    • Keep track of the current path from the root to the current node.
    • When reaching a leaf node, convert the current path to the required format and add it to the result list.
  2. String Construction:
    • Start from the root, and for each node visited, append its value to the path string.
    • Use recursion to traverse to the left and right children.
    • On reaching a leaf node, append the complete path string to the result list.
  3. Backtracking:
    • After exploring both the children of a node, backtrack to explore other paths, ensuring the path string is appropriately managed between recursive calls.

Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 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<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if (root) {
            findPaths(root, "", result);
        }
        return result;
    }

private:
    void findPaths(TreeNode* node, string path, vector<string>& result) {
        if (node) {
            path += to_string(node->val);
            
            // If it's a leaf, add the path to result
            if (!node->left && !node->right) {
                result.push_back(path);
            } else {
                path += "->"; // Add delimiter
                if (node->left) {
                    findPaths(node->left, path, result);
                }
                if (node->right) {
                    findPaths(node->right, path, result);
                }
            }
        }
    }
};

Time Complexity

This strategy ensures that all paths from the root to the leaves are found and formatted correctly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI