We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
publicstaticvoidpostOrder(Noderoot){// ensures all descendants of root that are right-children// (arrived at only by "recurring to right")// get inner-threaded// prefer not to give data,// but construction requires it as primitivefinalNodefakeNode=newNode(0);fakeNode.left=root;NodecurOuter=fakeNode;// in addition to termination condition,// also prevents fakeNode printingwhile(curOuter!=null){if(curOuter.left!=null){finalNodecurOuterLeft=curOuter.left;// Find in-order predecessor of curOuterNodecurOuterInOrderPred=curOuterLeft;while(curOuterInOrderPred.right!=null&&curOuterInOrderPred.right!=curOuter){curOuterInOrderPred=curOuterInOrderPred.right;}if(curOuterInOrderPred.right==null){// [Outer-] Thread curOuterInOrderPred// to curOutercurOuterInOrderPred.right=curOuter;// "Recur" on leftcurOuter=curOuterLeft;}else{// curOuterInOrderPred already [outer-] threaded to curOuter// -> [coincidentally] therefore curOuterLeft's left subtree is done processing// Prep for [inner] threading (which hasn't ever been done yet here)...NodecurInner=curOuterLeft;NodecurInnerNext=curInner.right;// [Inner-] Thread curOuterLeft [immediately backwards] to curOuter [its parent]curOuterLeft.right=curOuter;// [Inner-] Thread the same [immediately backwards] for all curLeft descendants// that are right-children (arrived at only by "recurring" to right)while(curInnerNext!=curOuter){// Advance [inner] Node refs down 1 level (to the right)finalNodebackThreadPrev=curInner;curInner=curInnerNext;curInnerNext=curInnerNext.right;// Thread immediately backwardscurInner.right=backThreadPrev;}// curInner, and all of its ancestors up to curOuterLeft,// are now indeed back-threaded to each's parent// Print them in that order until curOuterwhile(curInner!=curOuter){/* -> VISIT */System.out.print(curInner.data+" ");// Move up one levelcurInner=curInner.right;}// "Recur" on rightcurOuter=curOuter.right;}}else{// "Recur" on rightcurOuter=curOuter.right;}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tree: Postorder Traversal
You are viewing a single comment's thread. Return to all comments →
Java - O(n) time, O(1) space
No recursion or stack - algorithm modified from Morris's for In-Order
(also see my https://stackoverflow.com/a/53645217/1357094)