Find ALL the paths in a binary tree equal to a sum


  • 0
    S

    This question was asked for an SDE 2 position.

    For example, given the following binary tree:

    [2,3,5,4,8,6,-2,null,null,null,null,null,null,null,2] and sum = 7

                                2
                              /     \
                            3         5
                         /     \    /   \
                        4       8  6     -2
                                          \
                                           2
    

    Print : [3,4] , [2,5] , [2,5,-2,2]


  • 0
    O

    From each node in the tree, find the paths that add up to the sum. As a node is traversed, decrease the sum being targeted. For a balanced tree, this runs in O(n log n).

    #include <vector>
    
    // O(n log n) for a balanced tree.
    std::size_t gNodesVisited = 0;
    
    struct Node
    {
        int value;
        Node* left;
        Node* right;
    
        Node()
            : value(0), left(nullptr), right(nullptr)
        {
        }
    };
    
    // Find the paths that add up to the sum.  root's value must be taken.
    void findPathsWithSum2(Node* const root, const int sum,
        std::vector<int>& currPath, std::vector<std::vector<int>>& paths)
    {
        ++gNodesVisited;
    
        currPath.push_back(root->value);
        const int remainder = sum - root->value;
        if (0 == remainder)
        {
            paths.push_back(currPath);
        }
    
        if (root->left)
        {
            findPathsWithSum2(root->left, remainder, currPath, paths);
        }
        if (root->right)
        {
            findPathsWithSum2(root->right, remainder, currPath, paths);
        }
        currPath.pop_back();
    }
    
    // Find the paths that add up to the sum by trying every node in the tree as a
    // starting point.
    void findPathsWithSum(Node* const root, const int sum,
        std::vector<std::vector<int>>& paths)
    {
        if (nullptr == root)
        {
            return;
        }
    
        std::vector<int> currPath;
        findPathsWithSum2(root, sum, currPath, paths);
    
        findPathsWithSum(root->left, sum, paths);
        findPathsWithSum(root->right, sum, paths);
    }
    
    void main()
    {
        const int null = INT_MIN;
        const int binaryTree[]
            = { 2, 3, 5, 4, 8, 6, -2, null, null, null, null, null, null, null, 2 };
        const std::size_t size = sizeof(binaryTree) / sizeof(int);
        const int sum = 7;
    
        if (0 < size)
        {
            Node* const nodes = new Node[size];
            for (auto i = 0; i < size; ++i)
            {
                nodes[i].value = binaryTree[i];
                const std::size_t leftIndex = 2 * i + 1;
                if (leftIndex < size)
                {
                    if (null != binaryTree[leftIndex])
                    {
                        nodes[i].left = &nodes[leftIndex];
                    }
                }
                const std::size_t rightIndex = 2 * i + 2;
                if (rightIndex < size)
                {
                    if (null != binaryTree[rightIndex])
                    {
                        nodes[i].right = &nodes[rightIndex];
                    }
                }
            }
    
            std::vector<std::vector<int>> paths;
            findPathsWithSum(&nodes[0], sum, paths);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.