leetcode

commit f6adfd3d0d32487e8e45eaba341b80704227b3a9
parent c97ecf064b7843f9abe529b0a6e0638ec103ddd9
Author: Jack Sangdahl <jack@pngu.org>
Date:   Sun,  8 Feb 2026 21:16:25 -0700

1382. balance a binary search tree

Diffstat:
A
balance_binary_search_tree.c
 | 
60
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
balance_binary_search_tree.py
 | 
40
++++++++++++++++++++++++++++++++++++++++

2 files changed, 100 insertions(+), 0 deletions(-)
diff --git a/balance_binary_search_tree.c b/balance_binary_search_tree.c
@@ -0,0 +1,60 @@
+// 1382. Balance a Binary Search Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary search tree, return a balance binary search tree
+ * with the same node values. if there is more than one answer, return any of
+ * them. a binary search tree is balance if the depth of the two subtrees of
+ * every node never differs by more than 1.
+ */
+
+int depth(struct TreeNode *root) {
+  if (!root)
+    return 0;
+  return depth(root->left) + depth(root->right) + 1;
+}
+
+void inorder(struct TreeNode *root, struct TreeNode **arr, int *idx) {
+  if (!root)
+    return;
+  inorder(root->left, arr, idx);
+  arr[(*idx)++] = root;
+  inorder(root->right, arr, idx);
+}
+
+struct TreeNode *build(struct TreeNode **arr, int l, int r) {
+  if (l > r)
+    return NULL;
+  int m = l + (r - l) / 2;
+  struct TreeNode *node = arr[m];
+  node->left = build(arr, l, m - 1);
+  node->right = build(arr, m + 1, r);
+  return node;
+}
+
+struct TreeNode *balanceBST(struct TreeNode *root) {
+  if (!root)
+    return NULL;
+  int n = depth(root), idx = 0;
+  struct TreeNode **nodes =
+      (struct TreeNode **)malloc(n * sizeof(struct TreeNode *));
+  inorder(root, nodes, &idx);
+  struct TreeNode *ans = build(nodes, 0, n - 1);
+  free(nodes);
+  return ans;
+}
+
+int main() {
+  int r1i[] = {1, -1, 2, -1, 3, -1, 4, -1, -1};
+  int r2i[] = {2, 1, 3};
+  struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
+  struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
+  struct TreeNode *bbst1 = balanceBST(r1);
+  struct TreeNode *bbst2 = balanceBST(r2);
+  treenode_print(bbst1); // expect: 2 1 3 -1 -1 -1 4
+  treenode_print(bbst2); // expect: 2 1 3
+  treenode_free(r1);
+  treenode_free(r2);
+  treenode_free(bbst1);
+  treenode_free(bbst2);
+}
diff --git a/balance_binary_search_tree.py b/balance_binary_search_tree.py
@@ -0,0 +1,40 @@
+# 1382. Balance a Binary Search Tree
+from leetcode import treenode_build
+
+"""
+given the 'root' of a binary search tree, return a balance binary search tree
+with the same node values. if there is more than one answer, return any of
+them. a binary search tree is balance if the depth of the two subtrees of
+every node never differs by more than 1.
+"""
+
+
+class Solution(object):
+    def balanceBST(self, root):
+        """
+        :type root: Optional[TreeNode]
+        :rtype: Optional[TreeNode]
+        """
+
+        def inorder(node):
+            return inorder(node.left) + [node.val] + inorder(node.right) if node else []
+
+        def sorted_arr_bst(left, right):
+            if left > right:
+                return None
+            mid = left + ((right - left) >> 1)
+            root = TreeNode(vals[mid])
+            root.left = sorted_arr_bst(left, mid - 1)
+            root.right = sorted_arr_bst(mid + 1, right)
+            return root
+
+        vals = inorder(root)
+        return sorted_arr_bst(0, len(vals) - 1)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    r1 = treenode_build(vals=[1, None, 2, None, 3, None, 4, None, None])
+    r2 = treenode_build(vals=[2, 1, 3])
+    print(obj.balanceBST(r1))
+    print(obj.balanceBST(r2))