In this tutorial, i am going to discuss what is binary tree preorder traversal? How to implement binary tree preorder traversal with and without recursion.
Given the root of a binary tree, write a code to return the preorder traversal of its nodes’ values.
In this post, I am going to discuss a very famous interview problem validate binary search tree or in other words check if a binary tree is BST or not.
Given the root of a binary tree, We have to write a code to check if it is a binary search tree (BST) or not.
The property of a valid binary search tree (BST) is:
i) The left subtree of a node contains only nodes with keys less than the node’s key.
ii) The right subtree of a node contains only nodes with keys greater than the node’s key.
iii) Both the left and right subtrees must also be binary search trees.
For example –
In this problem, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Write a code to recover binary search tree without changing its structure.
The solution using O(n) space is pretty straight forward. Can you solve this problem using constant space?