In Order Successor in Binary Search Tree

by

The general way depends on whether you have a parent link in your nodes or not.

If you store the parent link

Then you pick:

  1. The leftmost child of the right child, if your current node has a right child. If the right child has no left child, the right child is your inorder successor.
  2. Navigate up the parent ancestor nodes, and when you find a parent whose left child is the node you’re currently at, the parent is the inorder successor of your original node.

If you have right child, do this approach (case 1 above):

inorder-when-right-child

If you don’t have a right child, do this approach (case 2 above):

inorder-when-no-right-child

If you don’t store the parent link

Then you need to run a complete scan of the tree, keeping track of the nodes, usually with a stack, so that you have the information necessary to basically do the same as the first method that relied on the parent link.

More Related Contents:

  1. How do you validate a binary search tree?
  2. What is the difference between tree depth and height?
  3. Hashing a Tree Structure
  4. How to create the most compact mapping n → isprime(n) up to a limit N?
  5. Reverse the ordering of words in a string
  6. Data structures for loaded dice?
  7. How to implement a queue using two stacks?
  8. How to efficiently build a tree from a flat structure?
  9. Store the largest 5000 numbers from a stream of numbers
  10. Computing set intersection in linear time?
  11. How to delete in a heap data structure?
  12. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  13. O(klogk) time algorithm to find kth smallest element from a binary heap
  14. Skip List vs. Binary Search Tree
  15. reconstructing a tree from its preorder and postorder lists
  16. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  17. Why DFS and not BFS for finding cycle in graphs
  18. Finding height in Binary Search Tree
  19. Print the biggest K elements in a given heap in O(K*log(K))?
  20. How can I return an array of struct in solidity?
  21. The intersection of all combinations of n sets
  22. Does C have any tools for doing string addition?
  23. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  24. Why use binary search if there’s ternary search?
  25. Algorithm for merging two max heaps?
  26. What are probabilistic data structures?
  27. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  28. Why is vector array doubled?
  29. Given a set of intervals, find the interval which has the maximum number of intersections
  30. Iterative tree walking

Leave a Comment