Divide Given Bst

easy

Unknown

Question Solve Solutions

You are given root of a BST and a targat value.
Divide this BST into 2 BST's such that
1) first BST contains all values smaller then and equal to target.
2) second BST contains all values higher then target

Input Format

Root of BST Integer target Note: given tree is balanced so you only need to use inorder traversal for tree generation

Output Format

RootNode of 2 BSTS

Constraints

The number of nodes in the tree is in the range [1, 50].
0 &lt;= Node.val, target &lt;= 1000

Notice

NA

Example

Input

1 2 3 4 5 6 7 8 9
4

Output

1 2 3 4 #5 6 7 8 9

Greater Smaller Pointer

Missing Element In Sorted Array

Related Questions

easy Is Prime easy Prime Till N easy Reverse Integer easy GCD easy Fibonacci easy Fib Till N easy Exit Point of a matrix easy Placing N Queen in a matrix easy Arranging Vowels And Consonants easy Addition Of Two Linked List easy Circular Linked List easy Sort The Absolute List easy Decimal Number From Binary Linked List easy Find the largest rectangle in a matrix easy Count Pairs Having Sum X easy Delete alternate nodes of linked list