Convert Binary Tree to BST
Mon Apr 22 2024 In-Order Traversal:
First, an in-order traversal of the binary tree is performed to extract all node values in a sorted manner since in-order traversal of a BST inherently results in a sorted sequence.
Array to BST Construction:
Using the sorted node values from the in-order traversal, a balanced BST is constructed. This is achieved by recursively selecting the middle element of the current sub-array to ensure balanced height, setting it as the root, and applying the same process to the left and right halves to construct the subtrees.
1class TreeNode {
2 constructor(val) {
3 this.val = val;
4 this.left = null;
5 this.right = null;
6 }
7 }
8
9 class Solution {
10 constructor() {
11 this.inorder = [];
12 }
13
14 binaryTreeToBST(root) {
15 this.inOrderTraversal(root);
16 return this.buildBST(0, this.inorder.length - 1);
17 }
18
19 inOrderTraversal(node) {
20 if (node) {
21 this.inOrderTraversal(node.left);
22 this.inorder.push(node.val);
23 this.inOrderTraversal(node.right);
24 }
25 }
26
27 buildBST(start, end) {
28 if (start > end) {
29 return null;
30 }
31
32 const mid = Math.floor((start + end) / 2);
33 const root = new TreeNode(this.inorder[mid]);
34
35 root.left = this.buildBST(start, mid - 1);
36 root.right = this.buildBST(mid + 1, end);
37
38 return root;
39 }
40 }
41
42
43 const root = new TreeNode(1);
44 root.left = new TreeNode(2);
45 root.right = new TreeNode(3);
46
47
48 const solution = new Solution();
49 const bstRoot = solution.binaryTreeToBST(root);
50
51
52 function printInOrder(node) {
53 if (node) {
54 printInOrder(node.left);
55 console.log(node.val);
56 printInOrder(node.right);
57 }
58 }
59
60 printInOrder(bstRoot);
61
62
63