Question 49926 in Javascript Question posted in
A very good W3school tutorial can be found here.

How can I convert an array to a binary tree with JavaScript?

I need a refresher on traversing trees.

I’m about to start interviewing, and tech interviewers LOVE to give binary tree questions. This one is a practice question from Hired.com. (I wouldn’t dare ask for this on an actual interview question posed to me – this is pure study. But it stumped me, and I know it shouldn’t have.)

Here’s an example question:

Given a binary tree represented as an array, (where a node of -1 is non-existent) write a function that determines whether the left or right branch of the tree is larger. The size of each branch is the sum of the node values. The function should return "Left" if the left side is larger, and "Right" if the right side is larger.

Here’s the problem. The sample array they’ve given is:

[3, 6, 2, 9, -1, 10]

which is supposed to represent a binary tree of:

     3
   /   
  6     2
 /     /
9    10

I just couldn’t figure out how to basically turn that array into the binary tree. I think I can create a binary tree just fine, but I’m not sure how to create a tree from an array like that. It’s one of those things I "used to know" but just for the life f me can’t figure out.

Here’s the code I’m working with (Javascript);

// went with a class, know I could probably do this FP, but f'it.
class TreeNode {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
  setLeft(node){
    this.left = node;
  }
  setRight(node){
    this.right = node;
  }
}

const buildNode = (root, valLeft, valRight){
  if(valLeft > 0){
    root.setLeft(new TreeNode(valLeft));
  }
  if(valRight > 0){}
    root.setRight(new TreeNode(valRight));
  }
  return root;
}

const solution = (arr) => {
  const rootNode = buildNode(new Node(arr.shift()), arr.shift(), arr.shift());
  /* this is where I run into trouble */
  if(arr.length){
    buildNode(rootNode.left, arr.shift(), arr.shift());
    buildNode(rootNode.right, arr.shift(), arr.shift());
    // I know I have to make a recursive function here,
    // and just can't wrap my head around it.  
  }
}
Tags:

4

Answers


  1. 0

    Given a binary tree represented as an array

    This is a bit underspecified–there are many ways an array can represent a binary tree. However, it is customary to do it in layers, i.e. from breadth-first-traversal. So array[0] is the root on the zeroth level, array[1] and array[2] are its children on the first level, array[3] and array[4] are the children on the second level of array[1] and so on.

    The nice thing about this representation is that you can easily get to the parent node by dividing the node index by 2, and get to the children by multiplying the node index by 2 (plus accounting for off-by-one errors depending on how you count). Also scaling the height of the tree aligns nicely with the typical allocation scheme for dynamic arrays.

    I’d solve the particular task as

    function solution(arr) {
  function getNode(index) {
    if (index >= arr.length || arr[index] == -1) return null;
    const node = new Node(arr[index]);
    node.setLeft(getNode((index+1)*2-1));
    node.setRight(getNode((index+1)*2));
    return node;
  }
  return getNode(0);
}
    Login or Signup to reply.
  2. 0

    I find a more FP version simpler:

    const makeTree = (nodes, i = 0) =>
  i >= nodes .length 
    ? null
    : {
        value: nodes [i] == -1 ? null : nodes [i], 
        left: makeTree (nodes, 2 * i + 1), 
        right: makeTree (nodes, 2 * i + 2)
      }

const sumTree = (node) => node == null 
  ? 0 
  : (node .value || 0) + sumTree (node .left) + sumTree (node .right)

const largerHalf = (
  nodes = [], 
  tree = makeTree (nodes), 
  lSum = sumTree (tree .left), 
  rSum = sumTree (tree .right)
) => lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal'

const nodes = [3, 6, 2, 9, -1, 10]

console .log (largerHalf (nodes)) //=> 'Left'

    • makeTree recursively converts an array into a tree format such as

      {
     value: 3,
     left: {
         value: 6,
         left: {value: 9, left: null, right: null},
         right: {value: -1, left: null, right: null}
     },
     right: {
         value: 2,
         left: {value: 10, left: null, right: null},
         right: null
     }
}

    • sumTree recursively totals up the values in a tree

    • largerHalf takes an array, converts it to a tree, sums that tree’s left and right subtrees, then reports which of them is larger

    The important thing here is makeTree, which will only work on balanced binary trees, but as that seems to be what the problem specifies, it shouldn’t be a problem. There’s a little extra handling for -1, but basically, we just use the representation of the tree in the array, where the children of node i are found at 2 * i + 1 and 2 * i + 2 and recur with those values to find the left and right subtrees. I think sumTrees and largerHalf should be clear enough. If not, please add a comment asking for more.

    If you don’t like the extra arguments in largerHalf (and there are some good reasons not to), then we can introduce a quick call function and write it like this:

    const call = (fn, ...args) => fn (...args)

const largerHalf = (nodes = []) => call (( 
  tree = makeTree (nodes), 
  lSum = sumTree (tree .left), 
  rSum = sumTree (tree .right)
) => lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal')

    or write a more imperative version like this:

    const largerHalf = (nodes = []) => { 
  const tree = makeTree (nodes)
  const lSum = sumTree (tree .left)
  const rSum = sumTree (tree .right)
  return lSum > rSum ? 'Left' : rSum > lSum ? 'Right' : 'Equal'
}
    Login or Signup to reply.
  3. 0

    I think the previous two answers misunderstand the tree->array construction. At least in the bigger versions I’ve seen, once a node is -1, it’s children are not given. Hence the children at index i are not necessarily 2i + 1 and 2i + 2.

    Also note that any extra -1’s at the end of the list are eliminated. So the last element of the list might be some node’s left child.

    The simplest solution I found is to keep a queue of nodes for which we’re waiting to read their children. As we create new nodes, we add them to the end of the queue. [If this were production code, I’d use a Deque, but for simplicity, I’m using a list.] When we run off the end of the list, the StopIteration terminates the loop.

    The hard part is building the tree. The other solutions show how to sum the left side, the right side, and determine which is bigger.

    @dataclass
class Node:
    value: int
    left: 'Node' = None,
    right: 'Node' = None,

def list_to_tree(list):
    if not list:
        # Return whatever you're supposed to return for an empty list
        return None
    iterator = iter(list)
    root = Node(value=next(iterator))
    queue = [root]
    try:
        while True:
            item = queue.pop(0)
            value = next(iterator)
            if value != -1:
                item.left = Node(value=value)
                queue.append(item.left)
            value = next(iterator)
            if value != -1:
                item.right = Node(value=value)
                queue.append(item.right)
    except StopIteration:
        return root

    Note that there are slightly more complicated but faster solutions. You don’t have to build the tree. You could instead keep a queue showing whether the next value to be read belongs to the left side of the tree or the right side of the tree. A single pass through the array gives you the left sum and the right sum, without actually building the tree.

    Login or Signup to reply.
  4. 0

    You don’t have to build the tree to calculate this, you can iterate over the input array and keep running totals and have a result in O(n). You only have to keep track of how many nodes there are in the left and right part of the tree at the current level (and subtract one if you come across a -1 value), so you know how many to expect in the next level.

    Consider this example:

    [1, 4, 6,-1, 8, 2, 3, 4, 6,-1,-1, 3, 9, 7,-1, 3,-1, 8,-1]
 -  L  R  L  L  R  R  L  L  R  R  R  R  L  L  L  L  R  R
sumL = 32
sumR = 31

    which would translate to this tree:

                1
           / 
          /   
         /     
        4       6
              / 
          8   2   3
         /      / 
        4   6   3   9
       /   /   /
      7   3   8

    The code below will solve it. You could further simplify it by not storing both sums, but just adding the left values and subtracting the right values, and seeing whether you end up above or below zero. You could also return early if one side has no nodes on the current level and the other side’s total is already greater.

    function largestSide(input) {
    var sum = [0,0];          // running total for left and right side
    var size = [1,1];         // size of left and right side at current level
    var side = 0;             // current side: 0=left, 1=right
    var count = 1;            // number of nodes at this side at current level
    var i = 0;                // current input element, first will be skipped

    while (++i < input.length) {
        if (input[i] == -1) --size[side];
        else sum[side] += input[i];
        if (--count == 0) {
            size[side] *= 2;
            if (size[1 - side]) side = 1 - side;
            count = size[side];
        }
    }
    return sum[0] > sum[1] ? "Left" : "Right";
}
document.write(largestSide([1, 4, 6,-1, 8, 2, 3, 4, 6,-1,-1, 3, 9, 7,-1, 3,-1, 8,-1]));
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search