javascript - Find parent node in binary tree from value in javascript

Question

I have the following tree structure:

class Binarytree {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }

  insertLeft(val) {
    this.left = val;
  }

  insertRight(val) {
    this.right = val;
  }
}

I'm trying to find a parent node from a node value. I created the function below:

const getParent = function(root, n, parent) {
  if (!root) return null;
  if (root.val === n) return parent;
  else {
    getParent(root.left, n, root);
    getParent(root.right, n, root);
  }
};

Here is my test case:

const tree = new BinaryTree(1);
const node2 = new BinaryTree(2);
const node3 = new BinaryTree(3);
const node4 = new BinaryTree(4);
const node5 = new BinaryTree(5);
node2.insertRight(node4);
node3.insertRight(node5);
tree.insertLeft(node2);
tree.insertRight(node3);

const test = getParent(tree, 4, tree);

It is always returning null.

标签： javascripttreebinary-tree

Answer 1

您需要返回嵌套调用getParent. 您可以使用逻辑 OR||链接调用 。

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

    insertLeft(val) {
        this.left = val;
    }

    insertRight(val) {
        this.right = val;
    }
}

const getParent = function(root, n, parent) {
    if (!root) return null;
    if (root.val === n) return parent;
    // return and chain with logical OR
    return getParent(root.left, n, root) || getParent(root.right, n, root);
}


const tree = new BinaryTree(1);
const node2 = new BinaryTree(2);
const node3 = new BinaryTree(3);
const node4 = new BinaryTree(4);
const node5 = new BinaryTree(5);
node2.insertRight(node4);
node3.insertRight(node5);
tree.insertLeft(node2);
tree.insertRight(node3);

const test = getParent(tree, 4, tree);
console.log(test);