Write 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

inOrderSucc

var inOrderSucc = function(node){
    var p = null;
    
    if (node !== null){
        if (node.parent === null || node.right !== null){
            p = leftMostChild(node.right);
            console.log("result=", p);
        } else {
            while ((p = node.parent) !== null){
                if (p.left === node){
                    break;
                } else {
                    node = p;
                }
            }
        }
    }
    return p;
}

var leftMostChild = function(node){
    if (node.left === null){
        return node;
    } else {
        return leftMostChild(node.left);
    }
}
    
var makeNode = function(value){
    var obj = { 
            value: value,
            parent: null,
            left: null,
            right: null};
    return obj;
}

// In the above diagram, inorder successor of 8 is 10, inorder successor of 10 is 12 and inorder successor of 14 is 20.

// tree
//                      20
//                      |
//                  8       22
//                  |       |    
//               4     12
//                     |
//                  10    14
// var root = makeNode("20");
// var node1 = makeNode("8");
// var node2 = makeNode("22");
// node1.parent = root;
// node2.parent = root;
// root.left = node1;
// root.right = node2;
// var node1 = makeNode("4");
// var node2 = makeNode("12");
// node1.parent = root.left;
// node2.parent = root.left;
// root.left.left = node1;
// root.left.right = node2;
// var node1 = makeNode("10");
// var node2 = makeNode("14");
// node1.parent = root.left.right;
// node2.parent = root.left.right;
// root.left.right.left = node1;
// root.left.right.right = node2;
// var node1 = makeNode("22");
// node1.parent = root;
// root.right = node1;
    
// var result = inOrderSucc(root.left.right.right);
// console.log(result.value);