110. Balanced binary tree

110_solution1.c

#include "tree_node.h"
#include <stdbool.h>
#include <stdlib.h>

// returns the subtree height, or -1 as soon as any subtree is unbalanced
static int height(struct TreeNode *node) {
  if (!node)
    return 0;

  int l = height(node->left);
  if (l == -1)
    return -1;

  int r = height(node->right);
  if (r == -1)
    return -1;

  if (abs(l - r) > 1)
    return -1;

  return 1 + (l > r ? l : r);
}

bool isBalanced(struct TreeNode *root) { return height(root) != -1; }

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

110_solution1.cpp

#include "tree_node.h"
#include <algorithm>
#include <cstdlib>

using namespace std;

class Solution {
public:
  bool isBalanced(TreeNode *root) { return height(root) != -1; }

private:
  int height(TreeNode *node) {
    if (!node)
      return 0;

    int l = height(node->left);
    if (l == -1)
      return -1;

    int r = height(node->right);
    if (r == -1)
      return -1;

    if (abs(l - r) > 1)
      return -1;

    return 1 + max(l, r);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

110_solution1.go

package trees

func isBalanced(root *TreeNode) bool {
    // returns the subtree height, or -1 as soon as any subtree is unbalanced
    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        l := height(node.Left)
        if l == -1 {
            return -1
        }

        r := height(node.Right)
        if r == -1 {
            return -1
        }

        if l-r > 1 || r-l > 1 {
            return -1
        }

        return 1 + max(l, r)
    }

    return height(root) != -1
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

110_solution1.java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    // returns the subtree height, or -1 as soon as any subtree is unbalanced
    private int height(TreeNode node) {
        if (node == null)
            return 0;

        int l = height(node.left);
        if (l == -1)
            return -1;

        int r = height(node.right);
        if (r == -1)
            return -1;

        if (Math.abs(l - r) > 1)
            return -1;

        return 1 + Math.max(l, r);
    }
}

TreeNode.java

// Definition for a binary tree node.
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;
    }
}

110_solution1.js

const TreeNode = require("./tree_node");

var isBalanced = function (root) {
  // returns the subtree height, or -1 as soon as any subtree is unbalanced
  const height = (node) => {
    if (!node) return 0;

    const l = height(node.left);
    if (l === -1) return -1;

    const r = height(node.right);
    if (r === -1) return -1;

    if (Math.abs(l - r) > 1) return -1;

    return 1 + Math.max(l, r);
  };

  return height(root) !== -1;
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

110_solution1.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # returns the subtree height, or -1 as soon as any subtree is unbalanced
        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            l = height(node.left)
            if l == -1:
                return -1

            r = height(node.right)
            if r == -1:
                return -1

            if abs(l - r) > 1:
                return -1

            return 1 + max(l, r)

        return height(root) != -1

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

110_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn is_balanced(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        Self::height(&root) != -1
    }

    // returns the subtree height, or -1 as soon as any subtree is unbalanced
    fn height(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match node {
            None => 0,
            Some(n) => {
                let n = n.borrow();

                let l = Self::height(&n.left);
                if l == -1 {
                    return -1;
                }

                let r = Self::height(&n.right);
                if r == -1 {
                    return -1;
                }

                if (l - r).abs() > 1 {
                    return -1;
                }

                1 + l.max(r)
            }
        }
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}