When passing an array down a binary tree traversal, how do I send separate arrays to the left and right branches?

Question

I am traversing a binary tree, and accumulating the values of visited nodes in an array . Code as follows:

function Node(val) {
    this.val = val;
    this.left = null;
    this.right = null;
}

function recurseArray(node,arr=[]){
    if(!node){
        return;
    }
    arr.push(node.val);
    console.log(`array at node ${node.val}: ${arr}`);
    recurseArray(node.left,arr);
    recurseArray(node.right,arr);
}

let n0 = new Node(0);
let n1 = new Node(1);
let n2 = new Node(2);
n0.left = n1;
n0.right = n2;

recurseArray(n0);

I was expecting to get this output:

array at node 0: 0
array at node 1: 0,1
array at node 2: 0,2

because I thought that a copy of the [0] version of the array would get passed separately to the two recurseArray() calls. But actually I get this output:

array at node 0: 0
array at node 1: 0,1
array at node 2: 0,1,2

It seems that instead it's the same pointer getting passed to the recurseArray() calls, so the changes made in the node.left call show up in the node.right call. Explicitly passing a copy using:

let leftCopy = [...arr];
let rightCopy = [...arr];
recurseArray(node.left,leftCopy);
recurseArray(node.right,rightCopy);

gives the desired output, but making a copy of the array at every recursive call is going to give this function a high time and space complexity (N² for both, i think?). Is there a more memory-efficient way to do this, or is this explicit copying the only way to get the output I need?

CertainPerformance · Accepted Answer · 2022-01-26 06:10:35Z

a copy of the array at every recursive call is going to give this function a high time and space complexity

Your desired output has N^2 complexity (worst-case) - for N nodes, you you'll be logging N arrays, where each array will have between 1 and N items. So there's nothing you could really do with the algorithm to get below that while still getting the desired result.

You could use strings instead of arrays, but that has the same sort of complexity issue, and would make the code harder to understand.

I suppose a tiny improvement would be to only create a new array when you need to change a value (and log), rather than creating a new array unconditionally before recursing.

function recurseArray(node,arrParam=[]){
    if(!node){
        return;
    }
    const arr = [...arrParam];
    arr.push(node.val);
    console.log(`array at node ${node.val}: ${arr}`);
    recurseArray(node.left,arr);
    recurseArray(node.right,arr);
}

rici · Accepted Answer · 2022-01-26 15:35:53Z

1

This is a backtracking algorithm, so it is important that when the recursive function returns, the persistent state (in this case, arr) has been restored to what it was when the function was entered.

You can do that by simply popping the element you pushed before returning:

function recurseArray(node,arr=[]){
    if(!node){
        return;
    }
    arr.push(node.val);
    console.log(`array at node ${node.val}: ${arr}`);
    recurseArray(node.left,arr);
    recurseArray(node.right,arr);
    arr.pop()
}

answered Jan 26, 2022 at 15:35

rici

243k30 gold badges263 silver badges364 bronze badges

Collectives™ on Stack Overflow

When passing an array down a binary tree traversal, how do I send separate arrays to the left and right branches?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related