I need help in understanding this interview question:

Q: find an algorithm to find the ‘next’ node (e.g., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

Does parent mean the in-order predecessor or just the immediate parent? How would one create a tree where the nodes have a link to the root node or inorder predecessor? Any help in understanding the data structure and the program below would be appreciated...

the solution (As posted in a form) is shown below:

```
public static TreeNode inorderSucc(TreeNode e) {
if (e != null) {
TreeNode p;
// Found right children -> return 1st inorder node on right
if (e.parent == null || e.right != null) {
p = leftMostChild(e.right);
} else {
// Go up until we’re on left instead of right (case 2b)
while ((p = e.parent) != null) {
if (p.left == e) {
break;
}
e = p;
}
}
return p;
}
return null;
}
public static TreeNode leftMostChild(TreeNode e) {
if (e == null) return null;
while (e.left != null) e = e.left;
return e;
}
```

When nodes store pointers to their parents, it almost always maeans their immediate parents and not their successors. The question in this interview is then how to navigate the tree to find the inorder successor.

The way to find an in order successor is to think about what would happen if you were to recursively do an in order walk of the tree, then to mimic what would happen next. In particular, the logic for an in order traversal always visits all of a node's left subtree, then the node itself, and then the right subtree. To find the in order successor, you need to see what case you're in.

If the node you're currently at has a right subtree, then the in order successor of that tree must be the very first node that would be visited in that subtree during an in order traversal, which is the smallest element of that tree. You can find this by descending into the right subtree, then marching down the left spine of the tree until you find the leftmost node.

If the node does not have a right subtree, then it's the largest node in some subtree. If you think about how the recursion works, the next step in an in order traversal would be to have all the recursive calls that just finished expanding their right subtrees return. Once this last frame returns, you'll visit the node of the first tree that expanded just its left subtree. Consequently, the in order successor of the node can be found by walking up the tree until you reach a node that's a left child. The parent of this node is then your successor. Alternatively, as an edge case, if you hit the root of the tree, that would also be your successor.

Hope this helps!

Similar Questions

What is the difference between binary search and binary search tree? Are they the same? reading the internet it seams the second is only for trees(up to 2 children nodes) and binary search doesn't fol

Is there a built in binary search tree in .NET 4.0, or do I need to build this abstract data type from scratch?

Me and my friend are doing some school work with programming in Python 3.1 and are VERY stuck. We're programming a binary tree and it's working fine except when we want to print all the nodes in inord

I am trying to create a program which which takes a list of words as an input, and sorts them into a binary tree, in order to allow them to be found, e.g. like a dictionary. This is what I have done s

What is the benefit of a binary search tree over a sorted array with binary search? Just with mathematical analysis I do not see a difference, so I assume there must be a difference in the low-level i

I'm trying to print out a binary tree I've build using inorder traversal, but I'm having trouble on defining how to pass values to the recursive function. Here is the error I'm getting: 1>methods.

I'm trying to write code for a binary search tree, the first method I'm working on is the add (insert) method. The root seems to insert properly, but I'm getting null pointer exception when adding the

I am having some problems printing an inOrder traversal of my binary tree. Even after inserting many items into the tree it's only printing 3 items. public class BinaryTree { private TreeNode root; pr

I am confused by this code: void in_order_traversal_iterative(BinaryTree *root) { stack<BinaryTree*> s; BinaryTree *current = root; while (!s.empty() || current) { if (current) { s.push(current)

I've just read about binary search trees from the Learn You a Haskell book, and I'm wondering whether it is effective to search more than one element using this tree? For example, suppose I have a b

I was reading through Introduction to algorithms i came across this problem about In-order Traversal of binary search tree without using a stack or recursion. Hint says to assume that testing of point

Ok so I thought it was fixed, but I'm getting totally inconsistent results. I rewrote it kind of from scratch to start fresh and here are my results. I get no errors, no crashing, it just doesn't remo

I have implemented a binary search tree and I want to add more functionality in its insertion function to make it a self-balancing tree. I am coding in C#. Can anybody please suggest me good tutorials

I'm making a Haskell function to delete a node from a Binary Search Tree. I know the rules regarding the action needed to be taken depending on the number children the targeted parent has. no children

Trying to make a contains function for a binary tree. The function looks like this: bool contains(bt_node* top, int data) { if (top == NULL) return false; else { if (data == top->data) return true

I'm trying to build a binary search tree given an ArrayList of sorted values. In trying to create the most efficient tree possible I take the middle value, and add it to the tree. Then recursively tak

Are there efficient methods for finding the number of all elements less than an element in a binary search tree? I've been trying to find a procedure or implementation in C++, but I haven't been able

Ok, I am trying to get a binary search tree to balance, and I know why it's not working, but I don't know how to fix it. This is what I have for my balancing methods. public void balance(){ if(isEmpt

Hi I am trying to print out level order of a binary search tree in the format (node element, parent node element). I am currently using queues to get the level order but I am having a hard time gettin

First off, this is homework, so putting that out there. I'm supposed to implement a binary search tree with specific methods: void insert(String), boolean remove(String), and boolean find (String). I

I'm trying to implement a structure which is basically a custom made hash table containing either nothing (NULL) or a pointer to a binary search tree object. Anyway, I'm having trouble figuring out ho

Functions in scheme/racket. Working on a few functions using a binary search tree. I have already defined helper functions to be: ;; returns value of node (define (value node) (if (null? node) '() (ca

I am getting an stack overflow when the program tries to add a number. It seems to be accessing a nonexistent binary search tree. Here is the error code: Unhandled exception at 0x01084DD9 in CIS 350 q

I need help understanding this homework assignment. I need to build a binary decision tree that finds all possible shifts for a job. Basically, you enter a job S and an array of numbers that represe

This is a grade 12 assignment. One of the questions asks us to write a method in BTree class that takes either a BNode or an integer, and removes the node from the tree. Here's what I've tried: public

Hi all, As per definition of Threaded binary tree given below A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and

I have 2 classes, NonEmptyTree and EmptyTree that implement the Tree interface. toString() method in NonEmptyTree class should return a string: key=>value key=>value key>value etc... I do not

How to convert a binary tree to binary search tree in-place, i.e., we cannot use any extra space.

I have been given two binary search trees. For example, A and B. Next, I was asked to delete the tree B from the tree A. By deletion, I mean delete all the nodes present in B from A. Note: B is not n

I am writing a c program to create threaded binary tree and then to find INORDER SUCCESSOR of a particular node. For this, i am displaying inorder sequence for the TBT constructed and then asking user

I am trying to understand how currying works in functional programming. I have gone through wiki and a couple of questions about the same on SO. Need help understanding lambda (currying) What is 'Cur

I am trying to figure out how to print the lowest k values in a binary search tree. I an having trouble stopping the method code: def kthSmallestBST(node,k, count): if node == None or count == k: retu

I can't figure out how to write a Binary Search Tree to file recursively. I open a BufferWriter with the file to wrtie too, in the Tree class. I then send the BufferWriter to the Node class to travers

I am trying to implement an inorder traversal which in every stage I'll get the current node. For example: ?- getnodesinorder(tree(1,nil,nil),X). X = 1 ; false. ?- getnodesinorder(tree(5,tree(4,tree(1

I was trying out an iterative method to find the height/depth of a binary search tree. Basically, I tried using Breadth First Search to calculate the depth, by using a Queue to store the tree nodes an

This is an interview Question. A binary search tree is given and the values of two nodes have been swapped. The question is how to find both the nodes and the swapped values in a single traversal of t

Disclaimer: This is for an assignment. I am not asking for explicit code answers, only help understanding why my code isn't working. I am trying to implement a basic Binary Search Tree, but I am havin

I have written the following code to check if a tree is a Binary search tree. Please help me check the code: Okay! The code is edited now. This simple solution was suggested by someone in the posts be

Im doing an assignment on building a binary tree from the preorder and inorder traversals (a char in each Node) and im trying to wrap my brain around how to build the actual tree. Here is my thought p

I am working on a function that searches through a binary search tree in C for a name that is passed in with the function. However, I am stuck on how to format my loop so that the recusion doesn't sim

I am trying to traverse a Binary Tree which is created in the following code. to be precise, the Binary Tree is a class and should include an iterator calling another function namely inorder(). this m

I've been researching how to create binary search trees and i have run into a problem when trying to create my own. I have to use the following private structure to create the tree. Every example that

I would like to find the most efficent way to check the node with minimum value in a Binary Search Tree. I'm not thinking to do it in a certain programming language right now, I would like just to thi

In Scheme, I can use define-struct to make a binary search tree, but how do you do it in Clojure?

For Binary tree: You no need to consider tree node values, I am interested about different tree topologies with 'N' nodes. For Binary Search Tree: We obviously consider tree node values.

Using Java, is it possible to write a recursive method to find an element in a binary search tree? I say no because of the nature of recursive re-tracing back unless I implemented incorrectly? I have

I need to add an item to a binary tree given only the item to be added. Here is the code I'm given: void BinaryTree::add(Data * data) { if (root == NULL) { root = new BinaryTreeNode(data); } else { r

What is the best way to store a binary search tree in Mysql ? Should each node be a table ?

I have to write an AVL tree for my data structures course and am stuck on calculating the balance factor for a subtree so that I know where and how to rotate the tree. Thanks, Eric edit: I know have t

My partner and I are implementing a Binary Search Tree for a Data Structures & Algorithms course. We are encountering issues with our add method. This code is shown below: public class BinarySearc