# The bottom up O(N) solution would be better

• It seems we should definitely use the bottom up approach

Additionally, in the first approach(Top down), I think we can add a hash map(`unordered_map<TreeNode*, int> depth`) to record the depth of the subtree of a node, to avoid repeated computation. Then we can reduce the average time complexity.

• My accepted 9ms solution, similar to your second method:

``````
class Solution {
int isBalanced(TreeNode* root, bool &balanced)
{
if (root == nullptr)
{
balanced = balanced && true;
return 0;
}
int d1 = isBalanced(root->left, balanced);
int d2 = isBalanced(root->right, balanced);
balanced = balanced && abs(d1 - d2) <= 1;
return 1 + max(d1, d2);
}
public:
bool isBalanced(TreeNode* root)
{
bool balanced = true;
isBalanced(root, balanced);
return balanced;
}
};``````

• @yangleizou

I think it should be O(nlogn) in average case, and O(n^2) in worse case.

• It's always fun to see that someone else came up with (roughly) the same algorithm!

Here's my version:

``````class Solution {
public:
bool isBalanced(TreeNode* root) {
return work(root, 0) != -1;
}

int work(TreeNode* node, int d) {
if (!node) return d;

int a = work(node->left, d+1);
int b = work(node->right, d+1);

return abs(a - b) <= 1 ? max(a, b) : -1;
}
};
``````

Note the return statement's conditional. (Try working out the possible values for `a` and `b` to prove its correctness).

• `````` bool isBalanced(TreeNode* root) {
if (root==nullptr)
return true;
if (abs((Deepth(root->left)-Deepth(root->right))<=1)
return isBalanced(root->left)&&isBalanced(root->right);
else
return false;
}
int Deepth(TreeNode* root) {
if (root = nullptr)
return 0;
return max(1+Deepth(root->left),1+Deepth(root->right));
}
``````

• Same ideas here. Basically, we can check the height while we are computing the node's height.

``````// O(n) time, O(H) space.
public:
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
private:
int checkHeight(TreeNode* root) {
if ( root == nullptr ) return 0;
int left = checkHeight(root->left);
if ( left == -1 ) return -1;
int right = checkHeight(root->right);
if ( right == -1 ) return -1;

if (abs(left - right) > 1) return -1;
else return max(left, right) + 1;
}
``````

• Time: O(n), Space: O(height) Iterative Solution

``````// Method 2: Iterative Solution (Post-order Traversal)
// Time: O(n)
// Space: O(height)
boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}

stack.offerLast(root);

//set to root not null to not confuse when root is misisng children
TreeNode prev = root;

while(!stack.isEmpty()) {
//get the next node to process, peek because we need to maintain trail until we return
TreeNode curr = stack.peekLast();

//if we just returned from left child
if (prev == curr.left) {
if (curr.right != null) {
//if we can go right go
stack.offerLast(curr.right);
} else {
//otherwise right height is -1 does not exist and combine heights
heights.offerLast(0);
if (!combineHeights(heights)) {
return false;
}
stack.pollLast(); //back to parent
}
} else if (curr.right == prev) { //if we just returned from right child
if (!combineHeights(heights)) {
return false;
}
stack.pollLast(); //up to parent
} else {
//this came from a parent, first thing is to visit the left child, or right if no left
if (curr.left != null) {
stack.offerLast(curr.left);
} else {
if (curr.right != null) {
//no left so when we combine this node left is 0
heights.offerLast(0);
//since we never go left above logic does not go right, so we must here
stack.offerLast(curr.right);
} else {
//no children set height to 1
heights.offerLast(1);
stack.pollLast(); //back to parent
}
}
}

prev = curr;
}

return true;
}

// Helper function: combineHeights
// pop both previous heights and make sure they are balanced,
// if not return false, if so return true and push the greater + 1
private boolean combineHeights(Deque<Integer> heights) {
int rightHeight = heights.pollLast();
int leftHeight = heights.pollLast();

if(Math.abs(leftHeight - rightHeight) > 1) {
return false;
} else {
heights.offerLast(Math.max(leftHeight, rightHeight) + 1);
return true;
}
}
``````

• @VV_Driven n*log(n) is the mean Time complexity. and the worst comlexity is T(n)=T(n-1)+1...O(n^2)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.