Successor

Problem Given a Binary Search tree, find the inorder successor of a node. Definition See the definition here. Examples Example 1: 10 / \ 5 30 / \ 22 35 ...

Can we perform inorder traversal on a binary tree without using recursion or a stack, while also keeping the space complexity constant? This is where Morris traversal comes in. We have seen inorder traversal of binary tree here - Binary Tree Traversal - Inorder. The iterative version involves stack. Now lets see Morris Traversal. The idea of Morris Traversal is based on Threaded Binary Tree. This approach achieves inorder traversal by establishing temporary links within the tree itself. The data is then printed by following these links, and finally, the tree structure is restored to its original state. ...