Revisiting Data structure Trees using JS

Was getting bored and wanted to check trees using data structure.

  1. Tree node leaf
function treenode(val, left, right)
{
    this.val = (val === undefined) ? 0: val;
    this.left = (left === undefined) ? null : left;
    this.right = (right === undefined) ? null : right;
}

2. Creation of a complete binary tree [level 3]

let nodeH = new treenode("H")
let nodeI = new treenode("I")
let nodeJ = new treenode("J")
let nodeK = new treenode("K")
let nodeL = new treenode("L")
let nodeM = new treenode("M")
let nodeN = new treenode("N")
let nodeO = new treenode("O")
let nodeD = new treenode("D",nodeH,nodeI)
let nodeE = new treenode("E",nodeJ,nodeK)
let nodeF = new treenode("F",nodeL,nodeM)
let nodeG = new treenode("G",nodeN,nodeO)
let nodeB = new treenode("B",nodeD,nodeE)
let nodeC = new treenode("C",nodeF,nodeG)
let root = new treenode("A",nodeB, nodeC);

3. Expected result –
PRE ORDER – ABDHIEJKCFLMGNO
IN ORDER – HDIBJEKALFMCNGO
POST ORDER – HIDJKEBLMFNOGCA

4. Preorder using recursion

function preorder(root, stack)
{
  if(root != null)
  {
    stack.push(root.val)    
    preorder(root.left,stack)
    preorder(root.right,stack)
  }
}

let stack = [];
preorder(root,stack);
console.log(stack.toString());

Similarly, Inorder and postorder can be done by changing order.

5. Preorder using interative

function preorder(root)
{
  let stack = [], res = [];

  stack.push(root);

  let result = "";
  while(stack.length > 0)
  {
    let poppedLeaf = stack.pop();
    result += poppedLeaf.val

    if(poppedLeaf.right != null)
      stack.push(poppedLeaf.right)
    
    if(poppedLeaf.left != null)
      stack.push(poppedLeaf.left)  
  }
  console.log(result)
}

preorder(root)

Leave a Reply

Your email address will not be published.