CODEWITHSUNDEEP
binary-treebinary-search-tree
user130744
user130744

Reputation: 31

How can I efficiently get to the leaves of a binary-search tree?

I want to sum all the values in the leaves of a BST. Apparently, I can't get to the leaves without traversing the whole tree. Is this true? Can I get to the leaves without taking O(N) time?

Upvotes: 2

Views: 2568

Answers (4)

Loren Pechtel
Loren Pechtel

Reputation: 9093

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

Upvotes: 3

Arnkrishn
Arnkrishn

Reputation: 30442

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

Upvotes: 1

Nick Lewis
Nick Lewis

Reputation: 4230

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.

Upvotes: 0

a_m0d
a_m0d

Reputation: 12205

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.

Upvotes: 1

Related Questions