CODEWITHSUNDEEP
c#algorithmtreebinary-search-tree
Saamer
Saamer

Reputation: 5119

Sum of nodes between two BST leaves

I am NOT looking for Maximum Sum Path of a tree. I can create and find the sum of the binary search tree, but I need to find the sum of all the nodes between two leaves.

For example, for the BST built with these nodes : 5, 10, 13, 8, 3, 4, 5, the tree looks like this : 

                         5
                     /       \
                   3           10
                    \         /  \
                     4       8    13
                            /
                           5

So if the input is 4 and 13, then the sum of nodes is 3+5+10=18.

The function could be something like this: Sum(tree, firstNumber, secondNumber);

I am thinking to create two ordered lists of all the nodes until the root node and seeing if any of them are common, and then just adding up the values of all the unique nodes. It's terrible in terms of time complexity and memory management, so I am looking to see if there's an easier way

Edit: M. Hazara is right, 5 is not a leaf. so I removed that example

Upvotes: 0

Views: 267

Answers (1)

Egodev
Egodev

Reputation: 91

Well, probably the first idea that comes to mind is to make a list for each node traveled for both leafs. However, since it's a Binary Search Tree (BST), the condition for which path to take is known and, therefore, is possible to track which nodes are in a common path and which aren't.

First of all, a BST search always starts from the root node, so it will always be part of the sum, assuming the BST has 3 nodes or more because we need two leafs. Secondly, it's essential to do a BST search for each leaf (firstNumber,secondNumber) to guarantee that we traveled each path's nodes, regardless if they are common or not. Finally, all that's left is to determine when a node is common in both paths, so we don't add the same value twice.

A node is in the common path if both BST searches take the same path. So, you will have to run both simultaneously inside your function. We can account all the common nodes in the sum by using a do-while:

firstCurrentNode = tree.Root;
secondCurrentNode = tree.Root;
do {
  sum += firstCurrentNode;
  // FirstNumber path check:
  if (firstNumber < firstCurrentNode) firstCurrentNode = firstCurrentNode.goLeftNode();
  else firstCurrentNode = firstCurrentNode.goRightNode();
  // SecondNumber path check:
  if (secondNumber < secondCurrentNod) secondCurrentNode = secondCurrentNode.goLeftNode(); 
  else secondCurrentNode = secondCurrentNode.goRightNode(); 
} while (firstCurrentNode == secondCurrentNode)

Once they are not equal, i.e, take different paths, due to the properties of a tree, they will never share a same path again. Therefore, we only need to continue the BST searches individually, including every node we find into the sum. However, we might have reached the leafs already, so it's necessary to check that first:

// Search for firstNumber
while(firstCurrentNode != firstNumber) {
  sum += firstCurrentNode;
  if (firstNumber < firstCurrentNode) firstCurrentNode = firstCurrentNode.goLeftNode();
  else firstCurrentNode = firstCurrentNode.goRightNode();
}
// Search for secondNumber
while(secondCurrentNode != secondNumber) {
  sum += secondCurrentNode;
  if (secondNumber < secondCurrentNod) secondCurrentNode = secondCurrentNode.goLeftNode(); 
  else secondCurrentNode = secondCurrentNode.goRightNode();
}

Of course, I assumed that the leafs used exists in the tree and all nodes contains unique values and you can make adjustments for that, but this is one way to get the sum without using more memory space or get worse performance.

Upvotes: 1

Related Questions