BST Inorder Successor in DSA Javascript - Build from Scratch

BST Inorder Successor

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the next bigger number after a given number in the tree. This is called the inorder successor.Imagine the BST as a family tree of numbers, where each number has smaller numbers on the left and bigger numbers on the right. Finding the inorder successor is like finding the next person in line after someone in a sorted list.

🎯 Goal: Build a program that finds the inorder successor of a given node value in a BST. You will create the BST nodes, set up the tree, write the logic to find the successor, and print the result.

📋 What You'll Learn

Create BST nodes with exact values and structure

Set a target node value to find its inorder successor

Implement the inorder successor logic using BST properties

Print the inorder successor value or 'null' if none exists

💡 Why This Matters

🌍 Real World

Finding the inorder successor is useful in database indexing, scheduling tasks in order, and navigating sorted data efficiently.

💼 Career

Understanding BST operations like inorder successor is important for software engineers working on search algorithms, data retrieval, and optimization problems.

1

Create BST nodes and build the tree

Create a class called Node with a constructor that takes value, left, and right parameters. Then create nodes with these exact values and structure:
root = new Node(20),
root.left = new Node(10),
root.right = new Node(30),
root.left.left = new Node(5),
root.left.right = new Node(15).

DSA Javascript

// Define Node class and create the BST nodes as described
// Your code here

Hint

Remember to create the Node class first, then build the tree by linking nodes with left and right.

2

Set the target node value to find successor

Create a variable called targetValue and set it to 10. This is the value of the node whose inorder successor you want to find.

DSA Javascript

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);

// Set the target node value
// Your code here

Hint

Just create a constant named targetValue and assign it the number 10.

3

Implement the inorder successor function

Write a function called inorderSuccessor that takes root and targetValue as parameters. Use a loop to find the node with targetValue. Then find its inorder successor using BST rules:
- If the node has a right child, the successor is the leftmost node in the right subtree.
- Otherwise, move up the tree to find the nearest ancestor for which the node is in the left subtree.
Return the successor node or null if none exists.

DSA Javascript

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);

const targetValue = 10;

// Write the inorderSuccessor function below
// Your code here

Hint

Use a loop to find the target node. Track a successor when moving left. If the node has a right child, find the leftmost node there. Otherwise, return the stored successor.

4

Print the inorder successor value

Call the inorderSuccessor function with root and targetValue. Then print the successor's value if it exists, or print null if there is no successor.

DSA Javascript

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

const root = new Node(20);
root.left = new Node(10);
root.right = new Node(30);
root.left.left = new Node(5);
root.left.right = new Node(15);

const targetValue = 10;

function inorderSuccessor(root, targetValue) {
  let successor = null;
  let current = root;

  // Find the target node
  while (current !== null) {
    if (targetValue  current.value) {
      current = current.right;
    } else {
      break;
    }
  }

  if (current === null) {
    return null; // target not found
  }

  // If right subtree exists, find leftmost node there
  if (current.right !== null) {
    current = current.right;
    while (current.left !== null) {
      current = current.left;
    }
    return current;
  }

  // Otherwise, successor is the ancestor stored
  return successor;
}

// Print the inorder successor value or null
// Your code here

Hint

Call inorderSuccessor(root, targetValue) and store the result. Then print the value of the result if it exists, otherwise print null.