Homepage | Alpha Codes

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