Find if two nodes are cousin nodes or sibling nodes in Binary Tree in JavaScript

Question

I know the idea is to first do level order traversal on the tree.

If the nodes are found on the same level and their parents do not match they are cousins.

And if matches they are siblings.

I can do level order traversal by

BinarySearchTree.prototype.levelOrderTraversal = function() {
    var q = [];
    var results = [];
    var _root = this.root;
    if(_root) {
        q.push(_root);
        while(q.length > 0) {
            var temp = q.shift();
            results.push(temp.value);
            if(temp.left) {
                q.push(temp.left);
            }
            if(temp.right) {
                q.push(temp.right);
            }
        }
        return results;
    }else {
        return null;
    }

}

But now how do I keep track of parents so that I can find given nodes are siblings or cousins?

For example,

if my level order traversal gives me

[3, 2, 4, 1, 5]

3 being root, 2 and 4 are siblings or parent 3.

1 is a left child of parent 2.

5 is a right child of parent 4.

so, 1 and 5 are cousin nodes while 2 and 4 are sibling nodes.

please add the tree object and the result, you like as data structure. — Nina Scholz
– Nina Scholz, Commented Oct 5, 2018 at 8:38
do you still want to take the same level traversal or another, like depth first? — Nina Scholz
– Nina Scholz, Commented Oct 5, 2018 at 9:29
@NinaScholz anything is fine I am just not sure which way to follow. I read somewhere level order can also be implemented, but anyway should be fine. — StrugglingCoder
– StrugglingCoder, Commented Oct 5, 2018 at 9:32

Nina Scholz · Accepted Answer · 2018-10-05 10:33:30Z

1

You could store the path to the wanted nodes and check the same length of the pathes and the last or the element before the last for getting the relation.

function getPath(node, value, path = []) {
    if (!node) {
        return;
    }
    if (node.value === value) {
        return path;
    }
    return getPath(node.left, value, path.concat(node.value))
        || getPath(node.right, value, path.concat(node.value));
}

function findRelation(root, a, b) {
    var pathA = getPath(root, a),
        pathB = getPath(root, b);

    if (pathA.length !== pathB.length) {
        return;
    }
    if (pathA.length && pathA[pathA.length - 1] === pathB[pathB.length - 1]) {
        return 'siblings';
    }

    if (pathA.length > 1 && pathA[pathA.length - 2] === pathB[pathB.length - 2]) {
        return 'cousins';
    }
}

var tree = { value: 3, left: { value: 2, left: { value: 1 } }, right: { value: 4, right: { value: 5 } } };

console.log(findRelation(tree, 2, 4));
console.log(findRelation(tree, 1, 5));

edited Oct 5, 2018 at 10:33

answered Oct 5, 2018 at 10:08

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

StrugglingCoder Over a year ago

Awesome. You are a true legend :) Such a different way of thinking :) Could you suggest me some things as to how to approach a problem in a different way altogether.

Nina Scholz Over a year ago

"Could you suggest me some things as to how to approach a problem in a different way altogether." ad hoc? what looks shorter to write. but seriously, you need how some things work, like trees, iteration and recursion. and if not known somthing, just try and try more times. that is the beauty about software/programming, you could try anything without harm.

Collectives™ on Stack Overflow

Find if two nodes are cousin nodes or sibling nodes in Binary Tree in JavaScript

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related