[JavaScript] Binary tree find successor

fast-coding.js

const assert = require('assert');

// Finding successor means, traverse the tree by inorder and the selected node's previous node is successor.
function findSuccessor(root, node) {
  // Right child exists, move to the left most child for right branch,
  // If the right child does not exists, successor will be rigth most parent,
  if (node.right !== null) return getLeftmostChild(node.right);

  return getRightmostParent(node);
}

function getLeftmostChild(node) {
  let currentNode = node;
  while (currentNode.left !== null) {
    currentNode = currentNode.left;
  }
  return currentNode;
}

function getRightmostParent(node) {
  let currentNode = node;
  while (currentNode.parent !== null && currentNode.parent.right === currentNode) {
    currentNode = currentNode.parent;
  }
  return currentNode.parent;
}


function BinaryTree(value) {
  this.value = value;
  this.parent = null;
  this.left = null;
  this.right = null;
}


/*
  tree = 1
        / \
       2   3
      / \
     4  5
    /
   6
   node = 5
   expected = 1
*/

const root = new BinaryTree(1);
root.left = new BinaryTree(2);
root.left.parent = root;
root.right = new BinaryTree(3);
root.right.parent = root;
root.left.left = new BinaryTree(4);
root.left.left.parent = root.left;
root.left.right = new BinaryTree(5);
root.left.right.parent = root.left;
root.left.left.left = new BinaryTree(6);
root.left.left.left.parent = root.left.left;
const node = root.left.right;
const expected = root;
const actual = findSuccessor(root, node);
assert.deepStrictEqual(actual, expected)

find-successor-optimized.js

const assert = require('assert');

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}
// O(h) time | O(1) space, where h is the height of the tree. 
function findSuccessor(tree, node) {
  if (node.right !== null)
    return getLeftmostChild(node.right);

  return getRightmostParent(node);
}

function getLeftmostChild(node) {
  let currentNode = node;
  while (currentNode.left !== null) {
    currentNode = currentNode.left;
  }
  return currentNode;
}

function getRightmostParent(node) {
  let currentNode = node;
  while (currentNode.parent !== null && currentNode.parent.right === currentNode) {
    currentNode = currentNode.parent;
  }
  return currentNode.parent;
}


/*
  tree = 1
        / \
       2   3
      / \
     4  5
    /
   6
   node = 5  
*/

const root = new BinaryTree(1);
root.left = new BinaryTree(2);
root.left.parent = root;
root.right = new BinaryTree(3);
root.right.parent = root;
root.left.left = new BinaryTree(4);
root.left.left.parent = root.left;
root.left.right = new BinaryTree(5);
root.left.right.parent = root.left;
root.left.left.left = new BinaryTree(6);
root.left.left.left.parent = root.left.left;
const node = root.left.right;
const expected = root;
const actual = findSuccessor(root, node);
assert.deepStrictEqual(actual, expected)

find-successor.js

const assert = require('assert');

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

// O(n) time | O(n) space - where n is node count in the tree,
function findSuccessor(tree, node) {
  const order = [];
  getInOrderTraversalOrder(tree, order)
  for (let i = 0; i < order.length; i++) {
    const currentNode = order[i];
    if (currentNode !== node) continue;

    if (i === order.length - 1) return null;

    return order[i + 1];
  }
}

// Left, root, right is in order.
function getInOrderTraversalOrder(node, order) {
  if (node === null) return order;
  if (node.left)
    getInOrderTraversalOrder(node.left, order);
  order.push(node)
  if (node.right)
    getInOrderTraversalOrder(node.right, order);
  return order;
}

/*
  tree = 1
        / \
       2   3
      / \
     4  5
    /
   6
   node = 5  
*/

const root = new BinaryTree(1);
root.left = new BinaryTree(2);
root.left.parent = root;
root.right = new BinaryTree(3);
root.right.parent = root;
root.left.left = new BinaryTree(4);
root.left.left.parent = root.left;
root.left.right = new BinaryTree(5);
root.left.right.parent = root.left;
root.left.left.left = new BinaryTree(6);
root.left.left.left.parent = root.left.left;
const node = root.left.right;
const expected = root;
const actual = findSuccessor(root, node);
assert.deepStrictEqual(actual, expected)