How can i get the leaves in a Binary search tree ?

Question

I want to sum all the values in the leafs in a BST, and i cant get the leafs without running all the tree...:(

Thanks Guys, but its only for academic purposes... i didn't want to "pay" O(N) to get the sum of all leafs, but it seems thats the only way.

Answer 1

There is no way to get the leaves of a tree without traversing the whole tree (especially if you want every single leaf), which will unfortunately operate in O(n) time. Are you sure that a tree is the best way to store your data if you want to access all of these leaves? There are other data structures which will allow more efficient access to your data.

Answer 2

You will either have to traverse the tree searching for nodes without children, or modify the structure you are using to represent the tree to include a list of the leaf nodes. This will also necessitate modifying your insert and delete methods to maintain the list (for instance, if you remove the last child from a node, it becomes a leaf node). Unless the tree is very large, it's probably nice enough to just go ahead and traverse the tree.

Answer 3

Hi

To access all leaf nodes of a BST, you will have to traverse all the nodes of BST and that would be of order O(n).

One alternative is to use B+ tree where you can traverse to a leaf node in O(log n) time and after that all leaf nodes can be accessed sequentially to compute the sum. So, in your case it would be O(log n + k), where k is the number of leaf nodes and n is the total number of nodes in the B+ tree.

cheers

Answer 4

You realize that the leaves themselves will be at least 1/2 of O(n) anyway?