100 Days of code #Day6
Today we are moving towards a tree structure, Binary Search Tree.
Binary Search Tree:
Tree is a hierarchical data structure with nodes and children and connections between them. Binary trees are ones which have at most 2 children ( 0 to 2 children)
Binary Search tree is a variation of binary tree which will be sorted and ordered in a way that the elements less than the value of root will be in the left and elements greater than value of root element will be on the right.
Given a non-empty array of integers representing the pre-order traversal of a
Binary Search Tree (BST), write a function that creates the relevant BST and
returns its root node.
The input array will contain the values of BST nodes in the order in which
these nodes would be visited with a pre-order traversal.
preOrderTraversalValues = [10, 4, 2, 1, 5, 17, 19, 18]
Looking at the problem it may seem pretty simple moving on left until the element is less than root and putting it in the right when greater but this approach will completely make the tree one sided. i.e instead of 17 being the right child of 10 it will become right child of 1
So we have to find when to move right (i.e from which index we have to move to right side of the tree).
So splitting the tree into two parts left and right and recursing the same through to the leaf level we can reconstruct the entire tree.