Sum of Descendant Nodes Below Target in Binary Search Tree
Given a Binary Search Tree with unique node values and a target value. You have to find the node whose data is equal to the target and return the sum of all descendant (of target) node’s data which are vertically below the target node. Initially, you are at the root node.
Note: If the target node is not present in bst then return -1.
Examples:
Input:
Target = 35
Output: 32
Explanation: Vertically below 35 is 32.Input:
Target = 25
Output: 52
Explanation: Vertically below 25 is 22, 30 and their sum is 52.
Approach: To solve the problem follow the below idea:
Idea is to use the property of the binary search tree. Check if the target value is present or not. If it is present return the sum of all descendant node’s data which are vertically below the target node else return -1.
Step-by-step approach:
- Implement a function to traverse down the BST and calculate the sum based on the given direction:
- If the direction is 0, add the node’s data to the result.
- Recursively traverse the left and right child nodes with updated directions (left: direction – 1, right: direction + 1).
- Implement a function to find the target node and calculate the sum vertically down from it:
- Start from the root and traverse the tree to find the target node by comparing data values.
- When the target node is found, set it as the target_node and calculate the sum vertically down from that node.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Define the structure of a // Binary Search Tree (BST) Node struct Node { int data; Node* left; Node* right; Node( int val) : data(val) , left(nullptr) , right(nullptr) { } }; // Variable to store the result long long int res; // Variable to store the target node Node* target_node; // Function to traverse down the BST and // calculate the sum based on the given direction void down(Node* node, int direction) { if (node) { // Add the node's data to the result // based on the direction if (direction == 0) res += node->data; // Traverse left and right child // nodes recursively down(node->left, direction - 1); down(node->right, direction + 1); } } // Function to find the target node and // calculate the sum vertically down from it void find(Node* node, int target) { // Check if the target node is null if (target_node == NULL) { if (node) { // If the node's data is greater than // the target, traverse left if (node->data > target) find(node->left, target); // If the node's data is smaller // than the target, traverse right else if (node->data < target) find(node->right, target); // If the node's data is equal to // the target, set target_node and // calculate the sum vertically down else { target_node = node; down(node, 0); } } } } // Function to calculate the sum vertically // down starting from the target node long long int verticallyDownBST(Node* root, int target) { // Initialize the result as -target and // target_node as null res = -target; target_node = NULL; // Find the target node and // calculate the sum find(root, target); // If the sum is still -target, return -1 // as there is no valid target node if (res == -target) return -1; // Return the final sum return res; } // Driver Code int main() { // Build a BST Node* root = new Node(25); root->left = new Node(20); root->right = new Node(35); root->left->left = new Node(15); root->left->right = new Node(22); root->right->left = new Node(30); root->right->right = new Node(45); root->right->right = new Node(45); root->right->left->right = new Node(32); // Define the target node value int target = 35; // Calculate the sum vertically down from // the target node long long int result = verticallyDownBST(root, target); // Output the result if (result != -1) cout << "Largest Sum Vertically Down from Target (" << target << "): " << result << endl; else cout << "No valid target node found." << endl; return 0; } |
Java
// Java code for the above approach public class VerticalSumBST { // Define the structure of a // Binary Search Tree (BST) Node static class Node { int data; Node left; Node right; Node( int val) { data = val; left = null ; right = null ; } } // Variable to store the result static long res; // Variable to store the target node static Node targetNode; // Function to traverse down the BST and // calculate the sum based on the given direction static void down(Node node, int direction) { if (node != null ) { // Add the node's data to the result // based on the direction if (direction == 0 ) res += node.data; // Traverse left and right child // nodes recursively down(node.left, direction - 1 ); down(node.right, direction + 1 ); } } // Function to find the target node and // calculate the sum vertically down from it static void find(Node node, int target) { // Check if the target node is null if (targetNode == null ) { if (node != null ) { // If the node's data is greater than // the target, traverse left if (node.data > target) find(node.left, target); // If the node's data is smaller // than the target, traverse right else if (node.data < target) find(node.right, target); // If the node's data is equal to // the target, set targetNode and // calculate the sum vertically down else { targetNode = node; down(node, 0 ); } } } } // Function to calculate the sum vertically // down starting from the target node static long verticallyDownBST(Node root, int target) { // Initialize the result as -target and // targetNode as null res = -target; targetNode = null ; // Find the target node and // calculate the sum find(root, target); // If the sum is still -target, return -1 // as there is no valid target node if (res == -target) return - 1 ; // Return the final sum return res; } // Driver Code public static void main(String[] args) { // Build a BST Node root = new Node( 25 ); root.left = new Node( 20 ); root.right = new Node( 35 ); root.left.left = new Node( 15 ); root.left.right = new Node( 22 ); root.right.left = new Node( 30 ); root.right.right = new Node( 45 ); root.right.right = new Node( 45 ); root.right.left.right = new Node( 32 ); // Define the target node value int target = 35 ; // Calculate the sum vertically down from // the target node long result = verticallyDownBST(root, target); // Output the result if (result != - 1 ) System.out.println( "Largest Sum Vertically Down from Target (" + target + "): " + result); else System.out.println( "No valid target node found." ); } } |
Python3
# Define the structure of a Binary Search Tree (BST) Node class Node: def __init__( self , val): self .data = val self .left = None self .right = None # Variable to store the result res = 0 # Variable to store the target node target_node = None # Function to traverse down the BST and calculate the sum based on the given direction def down(node, direction): global res if node: # Add the node's data to the result based on the direction if direction = = 0 : res + = node.data # Traverse left and right child nodes recursively down(node.left, direction - 1 ) down(node.right, direction + 1 ) # Function to find the target node and calculate the sum vertically down from it def find(node, target): global target_node # Check if the target node is null if target_node is None : if node: # If the node's data is greater than the target, traverse left if node.data > target: find(node.left, target) # If the node's data is smaller than the target, traverse right elif node.data < target: find(node.right, target) # If the node's data is equal to the target, set target_node and # calculate the sum vertically down else : target_node = node down(node, 0 ) # Function to calculate the sum vertically down starting from the target node def vertically_down_bst(root, target): global res, target_node # Initialize the result as -target and target_node as null res = - target target_node = None # Find the target node and calculate the sum find(root, target) # If the sum is still -target, return -1 as there is no valid target node if res = = - target: return - 1 # Return the final sum return res # Driver Code if __name__ = = "__main__" : # Build a BST root = Node( 25 ) root.left = Node( 20 ) root.right = Node( 35 ) root.left.left = Node( 15 ) root.left.right = Node( 22 ) root.right.left = Node( 30 ) root.right.right = Node( 45 ) root.right.left.right = Node( 32 ) # Define the target node value target = 35 # Calculate the sum vertically down from the target node result = vertically_down_bst(root, target) # Output the result if result ! = - 1 : print (f "Largest Sum Vertically Down from Target ({target}): {result}" ) else : print ( "No valid target node found." ) |
C#
using System; public class VerticalSumBST { // Define the structure of a Binary Search Tree (BST) Node public class Node { public int data; public Node left; public Node right; public Node( int val) { data = val; left = null ; right = null ; } } // Variable to store the result private static long res; // Variable to store the target node private static Node targetNode; // Function to traverse down the BST and // calculate the sum based on the given direction private static void Down(Node node, int direction) { if (node != null ) { // Add the node's data to the result // based on the direction if (direction == 0) res += node.data; // Traverse left and right child // nodes recursively Down(node.left, direction - 1); Down(node.right, direction + 1); } } // Function to find the target node and // calculate the sum vertically down from it private static void Find(Node node, int target) { // Check if the target node is null if (targetNode == null ) { if (node != null ) { // If the node's data is greater than // the target, traverse left if (node.data > target) Find(node.left, target); // If the node's data is smaller // than the target, traverse right else if (node.data < target) Find(node.right, target); // If the node's data is equal to // the target, set targetNode and // calculate the sum vertically down else { targetNode = node; Down(node, 0); } } } } // Function to calculate the sum vertically // down starting from the target node private static long VerticallyDownBST(Node root, int target) { // Initialize the result as -target and // targetNode as null res = -target; targetNode = null ; // Find the target node and // calculate the sum Find(root, target); // If the sum is still -target, return -1 // as there is no valid target node if (res == -target) return -1; // Return the final sum return res; } // Driver Code public static void Main() { // Build a BST Node root = new Node(25); root.left = new Node(20); root.right = new Node(35); root.left.left = new Node(15); root.left.right = new Node(22); root.right.left = new Node(30); root.right.right = new Node(45); root.right.right = new Node(45); root.right.left.right = new Node(32); // Define the target node value int target = 35; // Calculate the sum vertically down from // the target node long result = VerticallyDownBST(root, target); // Output the result if (result != -1) Console.WriteLine( "Largest Sum Vertically Down from Target (" + target + "): " + result); else Console.WriteLine( "No valid target node found." ); } } |
Javascript
// Define the structure of a Binary Search Tree (BST) Node class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } // Variable to store the result let res = 0; // Variable to store the target node let target_node = null ; // Function to traverse down the BST and calculate the sum based on the given direction function down(node, direction) { if (node) { // Add the node's data to the result based on the direction if (direction === 0) { res += node.data; } // Traverse left and right child nodes recursively down(node.left, direction - 1); down(node.right, direction + 1); } } // Function to find the target node and calculate the sum vertically down from it function find(node, target) { // Check if the target node is null if (target_node === null ) { if (node) { // If the node's data is greater than the target, traverse left if (node.data > target) { find(node.left, target); } // If the node's data is smaller than the target, traverse right else if (node.data < target) { find(node.right, target); } // If the node's data is equal to the target, set target_node and // calculate the sum vertically down else { target_node = node; down(node, 0); } } } } // Function to calculate the sum vertically down starting from the target node function verticallyDownBST(root, target) { // Initialize the result as -target and target_node as null res = -target; target_node = null ; // Find the target node and calculate the sum find(root, target); // If the sum is still -target, return -1 as there is no valid target node if (res === -target) { return -1; } // Return the final sum return res; } // Driver Code // Build a BST let root = new Node(25); root.left = new Node(20); root.right = new Node(35); root.left.left = new Node(15); root.left.right = new Node(22); root.right.left = new Node(30); root.right.right = new Node(45); root.right.left.right = new Node(32); // Define the target node value let target = 35; // Calculate the sum vertically down from the target node let result = verticallyDownBST(root, target); // Output the result if (result !== -1) { console.log(`Largest Sum Vertically Down from Target (${target}): ${result}`); } else { console.log( "No valid target node found." ); } |
Largest Sum Vertically Down from Target (35): 32
Time complexity: O(h), where ‘h’ is the height of the tree. In a balanced BST, it is O(log n), while in the worst case (skewed tree), it can be O(n).
Auxiliary space: O(h),