MHB Find Next Smallest & Greatest Key in BST

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Element
AI Thread Summary
In a binary search tree, finding the next greatest and smallest keys involves understanding in-order traversal, which follows the left subtree, current node, and then right subtree. For a node with a right child, the next greatest key is the leftmost child of that right subtree. If there is no right child, backtrack to the parent; if the node is a left child, the parent is the next greatest key, otherwise continue backtracking until a left child is found. Conversely, for the next smallest key, if a node has a left child, the next smallest key is the rightmost child of that left subtree. If there is no left child, backtrack to the parent; if the node is a right child, the parent is the next smallest key, otherwise continue backtracking until a right child is found. This method ensures accurate identification of the next keys in the binary search tree.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

We consider a Binary search tree and we want to find the element with the next greatest and the next smallest key than the key of a node v.

For example, how can we find the next of the node to which q1 points in the in-order traversal?

How will we find the next of the node to which q2 points, in the in-order traversal?

View attachment 3877Will it be as follows?

If we have a pointer to the root, the element with the next smallest key will be the rightmost child of the left subtree of the root and the element with the next greatest key will be the leftmost child of the right subtree of the root.

If we have a pointer to a node v of which the key is smaller than this of the root, then the rightmost child of the left subtree of v will have the key with the next smallest element and the first right child will have the next greatest key.

If we have a pointer to a node v of which the key is greater than this of the root, then the rightmost child of the left subtree of v will have the key with the next smallest element and the leftmost child of the right subtree will have the next greatest key.

Or have I understood it wrong? (Thinking)
 

Attachments

  • pPUa3.png
    pPUa3.png
    5.5 KB · Views: 86
Last edited:
Technology news on Phys.org


Hello!

Your understanding of finding the next greatest and smallest keys in a binary search tree is generally correct. However, there are a few clarifications that can be made.

First, it is important to note that in-order traversal in a binary search tree follows the pattern of left subtree, current node, right subtree. So, in order to find the next greatest and smallest keys, we need to consider the nodes in the order of left, current, and then right.

In the case of q1, if the node to which it points has a right child, then the next greatest key will be the leftmost child of that right subtree. If the node does not have a right child, then we need to backtrack to its parent and check if it is a left child. If it is, then the parent node will have the next greatest key. If it is a right child, we need to backtrack further until we find a node that is a left child, and that node will have the next greatest key.

For q2, we need to follow a similar approach. If the node to which it points has a left child, then the next smallest key will be the rightmost child of that left subtree. If the node does not have a left child, then we need to backtrack to its parent and check if it is a right child. If it is, then the parent node will have the next smallest key. If it is a left child, we need to backtrack further until we find a node that is a right child, and that node will have the next smallest key.

I hope this helps clarify any confusion. Let me know if you have any further questions.
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top