Balanced Binary Tree
Post
Cancel

# LeetCode #110: Balanced Binary Tree (C/C++).

easy

source: https://leetcode.com/problems/balanced-binary-tree
C/C++ Solution to LeetCode problem 110. Balanced Binary Tree.

## Problem

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

## Examples

### 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

Input: root = []
Output: true

## Constraints

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

## Solution

We will use recursion to perform a DFS (Depth First Search) in order to determine the heigh of each subtree.

• We call the recursive method with the root node.
• If the current node doesn’t exist, return 0.
• Explore the left and right nodes.
• If the absolute difference of nodes’ depth is higher than 1, we return -1.
• If the the depth of the left or right node is -1, we return -1 for the current node.
• Otherwise, we return the max hight of the nodes (left vs right) plus 1.
• If the final result == -1 then the tree is unbalanced.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 /** * 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) {} * }; */ class Solution { private: int exploreNode(TreeNode* node) { if (node == nullptr) return 0; int lH = exploreNode(node->left); int rH = exploreNode(node->right); if (lH == -1 || rH == -1 || abs(lH - rH) > 1) return -1; return max(lH, rH) + 1; } public: bool isBalanced(TreeNode* root) { int r = exploreNode(root); return r != -1; } };