Balanced BST.md

Problem

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -10^4 <= Node.val <= 10^4

solution.cs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsBalanced(TreeNode root) {
        if (root == null)
            return true;
        
        return (Math.Abs(calculateHeight(root.left) - calculateHeight(root.right)) <= 1) && IsBalanced(root.left) && IsBalanced(root.right);
    }
    
    int calculateHeight(TreeNode root) {
        if (root == null)
            return 0;
        
        int leftHeight = calculateHeight(root.left);
        int rightHeight = calculateHeight(root.right);
        return 1 + Math.Max(leftHeight, rightHeight);
    }
}

solution.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        
        return (Math.abs(calculateHeight(root.left) - calculateHeight(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
    }
    
    int calculateHeight(TreeNode root) {
        if (root == null)
            return 0;
        
        int leftHeight = calculateHeight(root.left);
        int rightHeight = calculateHeight(root.right);
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

solution.kt

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun isBalanced(root: TreeNode?): Boolean {
        if (root == null) { return true }
        
        return (Math.abs(calculateHeight(root.left) - calculateHeight(root.right)) <= 1) && isBalanced(root.left) && isBalanced(root.right)
    }
    
    fun calculateHeight(root: TreeNode?): Int {
        if (root == null) { return 0 }
        
        val leftHeight = calculateHeight(root.left)
        val rightHeight = calculateHeight(root.right)
        return 1 + maxOf(leftHeight, rightHeight)
    }
}

solution.swift

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isBalanced(_ root: TreeNode?) -> Bool {
        guard let root = root else { return true }
        
        return abs(calculateHeight(root.left) - calculateHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right)
    }
    
    private func calculateHeight(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        let leftHeight = calculateHeight(root.left)
        let rightHeight = calculateHeight(root.right)
        return 1 + max(leftHeight, rightHeight)
    }
}