Search code examples
c++binary-search-tree

Maximum number of left nodes/children in a path

I am trying to find a way to output the amount of most left nodes found in a path. For example:BST Example

The max nodes in this Binary Search Tree would be 2 (Goes from 5 ->3->1 and excluding the root).

What is the best way to approach this?

I have seen this thread which is fairly similar to what I am trying to achieve.

Count number of left nodes in BST

but there is like one line in the code that I don't understand.

count += countLeftNodes(overallRoot.left, count++);

overallRoot.left

My guess is that it calls a function on the object, but I can't figure out what goes into that function and what it would return.

Any answers to these two questions would be appreciated.

Solution

  • The answer you linked shows how to traverse the tree, but you need a different algorithm to get your count, since as you have noted, that question is trying to solve a slightly different problem.

    At any given point in the traversal, you will have the current left count: this will be passed down the tree as a second parameter to countLeftNodes(). That starts with zero at the root, and is increased by one whenever you go into the left child of a node, but is set to zero when you enter the right node.

    Then for both the left and right traversals, you set the left count to the greater of its current value, and the return from the recursive call to countLeftNodes(). And then this final value is what you return from countLeftNodes()