algorithmbinary-search-treetree-traversalinorder# Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?

I'm trying to understand the rules for finding the inorder predecessor of a node in a binary search tree (BST).

If a node π₯ has a left subtree, the inorder predecessor is the largest value in that left subtree.

If node π₯ has no left subtree, the predecessor is one of its ancestors. But if node π₯ is the right child, then its parent p is its predecessor

Hereβs my specific question:

If node π₯ has no left subtree and is a left child of its parent, its parent π cannot be the predecessor because π is larger than π₯. In this case, we move up the tree to find the ancestor that is smaller than π₯, and that ancestor is π₯'s predecessor.

Take a look at this BST:

```
50
/ \
30 70
/ \
20 40
/
35
```

- Node π₯ = 35 has no left subtree and is the left child of its parent
- 40 (the parent) cannot be the inorder predecessor because it's larger than 35.
- We move up the tree to the parent of 40, which is 30.
- 30 is smaller than 35, so 30 is the inorder predecessor of 35.

Is it true that the inorder predecessor of node π₯ in this situation is always its grandparent, or could it be a more distant ancestor?

Solution

The node you seek is the closest (lowest) ancestor, for whom the node in question is a right-side descendant, if such ancestor exists.

**Example**

In a tree like this

```
4
\
8
/ \
7 9
/
6
/
5
```

the predecessor of 5 is 4, which is not its *grandparent* (that is 7).

It is, however, the closest *ancestor* of 5, for which 5 is its right-side descendant (for all closer ancestors, that is for 6, 7 and 8, the 5 is a left-side descendant).

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ξ©(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?