How to make binary tree from array in javascript?

Question

I have an array var array = [8,10,12,5,3,6];

Logic

First node would be root node.
If new node value is less or equal =< than parent node, It would be left node of parent node
If new node value is greater > than parent node, It would be right node of parent node

And I am trying to achieve output like below object:

{
   value:8,
   left:{
      value:5,
      left:{ value:3 },
      right:{value:6}
   },
   right:{
      value:10,
      right:{value:12}
   }
}

Which would be in image like this

I tried below code:

var arr = [8,10,12,5,3,6];
var root = arr[0];
var rv = {};
for (var i = 0; i < arr.length; i++){
    if(arr[i] < root){
    rv.left = arr[i];
  }else{
    rv.right = arr[i];
  }
}
console.log(rv);

Please help me to solve this.

And what is the output of the code you tried?

O.O.Balance
– O.O.Balance

2018-02-12 10:26:06 +00:00
Commented Feb 12, 2018 at 10:26 — O.O.Balance
– O.O.Balance, Commented Feb 12, 2018 at 10:26

Nina Scholz · Accepted Answer · 2018-02-12 18:34:34Z

14

You could use a Node instance for new nodes and a function for inserting nodes.

Then iterate the values and build a new tree.

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

function insertNode(tree, value) {
    var node = tree,
        key;
    while (node.value !== value) {
         key = value < node.value ? 'left' : 'right';
         if (!node[key]) {
             node[key] = new Node(value);
             break;
         }
         node = node[key];
    }
    return tree;
}

var array = [8, 10, 12, 5, 3, 6],
    tree = array.reduce((t, v) => t ? insertNode(t, v) : new Node(v), null);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Feb 12, 2018 at 18:34

answered Feb 12, 2018 at 10:34

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

3 Comments

Rick Over a year ago

you don't mention how the array should be serialized for this tree. Is it in order, postorder, preorder, or is it completely arbitrary?

Nina Scholz Over a year ago

@Rick, is it necessary?

Rick Over a year ago

In the code, from the tree can you convert it back to the original array as well? Otherwise, it seems like the tree and the array have no logical relationship to each other.

Redu · Accepted Answer · 2018-02-12 16:00:08Z

3

While it is close to Nina's answer i believe to be a little more concise;

var data = [8,10,12,5,3,6],
    tree;

function insertBinTree (t = {value: void 0, left: void 0, right: void 0}, n){
  t.value !== void 0 ? t.value > n ? t.left = insertBinTree(t.left,n)
                                   : t.right = insertBinTree(t.right,n)
                     : t.value = n;
  return t;
}

tree = data.reduce(insertBinTree, void 0);
console.log(tree);

.as-console-wrapper {
max-height: 100% !important
}

answered Feb 12, 2018 at 16:00

Redu

26.3k6 gold badges61 silver badges84 bronze badges

Comments

freelancer · Accepted Answer · 2018-02-12 10:27:10Z

1

Try something like this by recursive method

var binary = {};
var arr = [8,5,10,3,6,12];

function makeBinary(binary,number){
  if(binary.value === undefined){
    binary.value = number;
  }else if(number > binary.value){
    if(binary.right === undefined){
      binary.right = {value:number};  
    }else{
      binary.right = makeBinary(binary.right,number);
    }
  }else{
    if(binary.left === undefined){
      binary.left = {value:number};  
    }else{
      binary.left = makeBinary(binary.left,number);
    }
  }
  return binary;
}

for(let i in arr){
  makeBinary(binary,arr[i]);
}

console.log(binary);

answered Feb 12, 2018 at 10:27

freelancer

1,1645 silver badges12 bronze badges

Comments

Asaf Strilitz · Accepted Answer · 2020-01-31 13:37:26Z

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


class Bst{
    constructor(){
        this.root=null;
    }

    insert(val){
        let newNode= new Node (val)
        if (!this.root) this.root=newNode;
    let current =this.root;        
        while (true) {
            if(val === current.val) return undefined;
            if(current.val<val){
                if (current.right===null){
                    current.right=newNode;
                    return this
                }
                    else
                    current=current.right}
            if(current.val>val){
                if (current.left===null){
                    current.left=newNode;
                    return this
                }
                    else
                    current=current.left}
                
        }
        
    
    }
    print (){
        let all="Root=";
    let visit=(current=this.root)=>{
        if(!current.left && !current.right){
            if(all[all.length-1]<current.val)
                 all+=`,LeR${current.val}`
                 else
                 all+=`,LeL${current.val}`
                }
else{
    if(all[all.length-1]<current.val)
         all+=`,FR${current.val}`
         else
                  all+=`,FL${current.val}`
            }
       
   if (current.left) visit(current.left)
   if (current.right)  visit(current.right)
        }
        visit()
        all+=` ,valid bst:${this.isValidBST()}`
        return all

    }

 isValidBST(node=this.root, min = null, max = null) {
if (!node) return true;
if (max !== null && node.data >= max) {
  return false;
}
if (min !== null && node.data <= min) {
  return false;
}
const leftSide = this.isValidBST(node.left, min, node.data);
const rightSide = this.isValidBST(node.right, node.val, max);

return leftSide && rightSide;
    }

find(val){
    let found=false
    let innerFind=(current=this.root)=>{
    if (val>current.val) 
       if (current.right != null) return innerFind(current.right)
        if(val===current.val)
        found= true 
   else
      if (current.left != null)return innerFind(current.left)
        if(val===current.val)
            found= true 
    return found
        }
        return innerFind()
    }

}




let tree=new Bst

tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(3)
tree.insert(1)
tree.insert(6)
tree.insert(4)
tree.insert(7)
tree.insert(2)
tree.print()

Hi and welcome to stackoverflow, and thank you for answering. While this code might answer the question, can you consider adding some explanation for what the problem was you solved, and how you solved it? This will help future readers to understand your answer better and learn from it.
This implements a BST with functions like Insert print all and checking if valid BST and find(boolean but can be easily changed ) just copy and paste to console to see how it works.

vishnu · Accepted Answer · 2022-01-08 13:06:04Z

0

You can do this by technique is called recursion. make an array with the structure ( left_subtree, key, right_subtree) in your case var array = [[3,5,6],8,[null,10,12]

class TreeNode {
    constructor(key) {
        this.key = key;
        this.right = null;
        this.left = null;
    }
}

function parseTuple(data) {
    if (data === null) {
        let node = null;
        return node;
    }
    else if (data.length === 3) {
        let node = new TreeNode(data[1]);
        node.left = parseTuple(data[0]);
        node.right = parseTuple(data[2]);
        return node;
    }
    else {
        let node = new TreeNode(data);
        return node;
    }

}

answered Jan 8, 2022 at 13:06

vishnu

212 bronze badges

Collectives™ on Stack Overflow

How to make binary tree from array in javascript?

5 Answers 5

3 Comments

Comments

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related