Question

Given a BST and a sum, write pseudo code to determine if the tree has a root- to-leaf path such that adding up all the values along the path equals the given sum. Given the below BST and sum = 49, the array is (8, 4, 10, 1, 0, 3, 9, 15, 16). Return true, as there exist a root-to-leaf path 8− > 10− > 15− > 16 which sum is 49.

Answer 1

Pseudocode

==================

Input:

• BST root node
• sum used to determine if the tree has a root- to-leaf path

Output:

Returns true if the tree has a root to leaf path with given sum, else false

function haspathSum (Node root, sum)

    {

        if (node is null) {

            return true if sum = 0

}

        else {

ans = false;

subsum = sum - node.data;

            if (subsum is 0 and node.left is null and node.right is null)

                return true;

            if (node.left is not null)

                ans = (ans) OR (haspathSum(node.left, subsum));

            if (node.right is not null)

                ans = (ans) OR haspathSum(node.right, subsum));

            return ans;

        }

    }