Tree Algorithms

We will revisit few basic algorithms in this page:

• Tree Traversal

( Recursive and iterative)

• Morris Inorder Traversal
• TreeToList and ListToTree

Tree Traversal

    

         for inorder tree traversal

    

        public void inorder(TreeNode node) {

              if(node == null) return;

              inorder(node.left);

              print(node.val);

              inorder(node.right);

        }

        

         public void inorder(TreeNode node) {

               if(node == null) return;

               Stack<TreeNode> st = new Stack<TreeNode>();

               TreeNode cur = node;

               while( cur != null || st.Count() > 0) {

                   while(cur != null) {

                      st.Push(cur);

                      cur = cur.left;  

                   }

                  cur  = st.Top(); st.Pop();

                  Print(cur.val);

                  cur = cur.right;

              }

        } 

     PreOrder

      

      public void preorder(TreeNode root) {

            if(root == null) return null;

            Print(root.val);

            preorder(root.left);

            preorder(root.right);

        }

   public void preorder(TreeNode root) {

        if(root == null) return;

        Stack<TreeNode> st = new Stack<TreeNode>();

        st.Push(root);

        while(st.Size() > 0) {

              TreeNode cur = st.Top(); st.Pop();

              print(cur);

             if(cur.right != null) st.Push(cur.right);

             if(cur.left != null) st.Push(cur.left);

         }

   }

   

PostOrder is reverse of PreOrder