Есть ли возможность добавить обратный указатель на родителя в древовидной структуре?

Question

Я пытаюсь создать структуру, которая выглядит как двоичное дерево. Где мне нужно установить обратные указатели, чтобы каждый узел мог быть связан со своим родителем, и как это повлияет на производительность?

function Node(expression, trueStatement, falseStatement) {
    this.expression = expression;
    this.trueStatement = trueStatement
    this.falseStatement = falseStatement
    this.left = null;
    this.right = null;
    this.back = null;
}

function BinarySearchTree() {
    this.root = null;
}

BinarySearchTree.prototype.push = function(state, expression, trueStatement, falseStatement) {
    var root = this.root;

    if (trueStatement == "") {
        trueStatement = false;
    }
    if (falseStatement == "") {
        falseStatement = false;
    }

    if (!root) {
        this.root = new Node(expression, trueStatement, falseStatement);
        return;
    }



    var currentNode = root;
    var newNode = new Node(expression, trueStatement, falseStatement);

    while (currentNode) {
        if (state) {
            if (!currentNode.left) {
                currentNode.left = newNode;
                break;
            } else {
                currentNode = currentNode.left;
            }
        } else {
            if (!currentNode.right) {
                currentNode.right = newNode;
                break;
            } else {
                currentNode = currentNode.right;
            }
        }
    }

}
var bst = new BinarySearchTree();
bst.push(true, "IIF()", "", "@user");
bst.push(false, "IIF()1", "@user", "");
bst.push(true, "IIF()2", "@user", "");

Цель состоит в том, чтобы каждый узел был связан с их родителями.

Answer 1

Добавьте свойство parent / back к вашему объекту Node и заполните, когда вы создаете Node.и где у вас есть

currentNode.left = newNode;

и добавьте

 currentNode.left = newNode;
 newNode.back = currentNode;

Реализуйте ту же логику в других местах