Modified Preorder Traversal (Recursive)183 views

AlgoPill 
 function modifiedPreOrderTraversal(root){
    /**
     * inner recursive function 
     * Node:{val:number,left:Node,right:Node}
     * sample input
     * var tree={ val:"F",
     *                 left:{ val:"B",
     *                        left:{ val:"A" },
     *                                right:{ val:"D",
     *                                          left:{val:"C"},
     *                                          right:{val:"E"}
     *                              }
     *                      },
     *                right:{val:"G",
     *                         right:{ val:"I",
     *                                   left:{val:"H"}
     *                                 }
     *                       }
     *   };
     */
    function mptt(root,counter){
        if(root){
            root.first= counter.count++;
            mptt(root.left,counter);
            mptt(root.right,counter);
            root.second=counter.count++;
        }
        return root;
    }
    return mptt(root,{count:1});
}

Problem Statement: Given a binary tree find its Modified Pre-order Traversal.

Solution:  Modified Preorder Traversal (MPTT) is an implementation of Nested Set Model. In this implementaion tree is traversed in preoder traveresal, i.e. root first then , its left child and finally its right child. In MPTT each node is visited twice and two numbers associated with each node. If first number is n then second number is [n+(2*no_children)+1].  Thus while numbering a node N, with set the first number to x, then we visit all its children from left to right assigning , first and second numbers to each and keep incrementing the counter in the process, then we visi the node N again and assign the current value of counter as second number. In the given algorithm. We first start with number1 with node root and assign root.start=1, then we recursively number its left children and the its right children , then we come back and set root.second to current value of the counter.

Post a Comment

You must be logged in to post a comment.