Recover Binary Search Tree Problem Problem You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? Example Example 1: Input: *1 / *3 \ 2 Output: *3 / *1 \ 2 ...
Problem Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it. Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree. Examples Example 1: 1 / \ 2 3 / 4 ...
Problem Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST. ...
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. ...
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: ...