Traversal

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. ...

Binary Tree Cameras Problem Problem You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children. Return the minimum number of cameras needed to monitor all nodes of the tree. Examples Example 1: ...

Problem Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column). Examples Example 1: ...

Problem Given a node in a binary tree. Find the rightmost cousin of the give node. Examples Example 1 Let’s start with an example. 1 / \ 2 3 / / \ 4 5 6 \ / 7 8 ...

Problem Given the root of a binary tree, flatten the tree into a “linked list”: The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The “linked list” should be in the same order as a pre-order traversal of the binary tree. Examples Example 1: ...

Problem Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST. Examples Example 1: ...