Running starter_bintree.js

// CPCS 223 Analysis & Design of Algorithms
// Binary trees starter - binary tree divide-conquer
// 2021, Dr. Muhammad Al-Hashimi


/* Complete the object (fill code)

   o Use tree height from textbook as a template to develop algorithms for
     counting leaves and various tree traversals

   o Add code in the following functions to implement the algorithms as methods
     of the tree object at the bottom, insert code to count empty tree checks
     (external nodes) and compare to theory

   o Google more inorder, preorder and postorder lists to test your algorithms
     (try Figure 5.6)
     
   o (Advanced) Add a method to count nodes in the tree

*/

// ref. (as of 1/14/2020) https://www.techiedelight.com
var inorder =   [4,2,1,7,5,8,3,6];
var postorder = [4,2,7,8,5,6,3,1];

// construct a test binary tree from the inorder and postorder lists

var b = new BNTree(inorder, postorder);
// var b = new BNTree();   // create an empty tree example

// type: b.root in the console to browse the tree
document.write("Type: <code>b.root</code> in the console to browse the tree, or <code>b.height()</code> to call method");



// -----------------------------------------------------------------------
// student functions go here (don't change function names)


// ------------------------
function bntHeight(tree)    // use as example, note recursive call
{
   if ( tree == null )
      return -1;
   else
      return Math.max( bntHeight(tree.left), bntHeight(tree.right) ) + 1;
}

// ------------------------
function bntLeafCount(tree)
{

}

// ------------------------
function inTraversal(tree)    // hint: output visited node item to the console
{

}

// ------------------------
function postTraversal(tree)
{

}

// ------------------------
function preTraversal(tree)
{

}

// -----------------------------------------------------------------------
// utility code, only need to note object and method names to call


// Node object

function BNTNode(item)
{
   this.item = item;
   this.left = null;
   this.right = null;
}

// ------------------------
// General binary tree object

function BNTree(inorder, postorder)
{
   // object methods (write functions in student section above to implement behaviors)

   this.height    = function () { return bntHeight(this.root) };     // tree height
   this.leafCount = function () { return bntLeafCount(this.root) };  // count leaves
   this.nodeCount = function () { return bntNodeCount(this.root) };  // count Nodes
   this.inorder   = function () { inTraversal(this.root) };          // inorder traversal
   this.postorder = function () { postTraversal(this.root) };        // postorder traversal
   this.preorder  = function () { preTraversal(this.root) };         // preorder traversal


   // ignore internal utility code ---------------------------------------------------

   this.root = (function(inor, post)   // create a tree from inorder and postorder lists
   {
      if (inor===undefined || post===undefined) return null;  // init empty tree if no args

      // ref. (as of 1/14/2020) https://www.techiedelight.com

      var map = [], n = inor.length;
      for (var i=0; i<n; i++)
         map[inor[i]] = i;
      var poIndex = n - 1;
      return make2(0, poIndex);

      function make2(start, end)
      {
         if (start > end)
            return null;
         var root = new BNTNode(post[poIndex--]);
         var inIndex = map[root.item];
         root.right = make2(inIndex+1, end);
         root.left  = make2(start, inIndex-1);
         return root;
      }

   }) (inorder, postorder);   // end ignore utility code -----------------------------

}