Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Check Balanced

problem

Implement a function to check if a binary tree is balanced.

how to solve

A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. So I implement a function fetchHeight to get the heights of subtrees. To use a past result of fetchHeight function, I used hash table. If I calculate the height once before. I can get this value in O(1). To calculate the all of the value of fetch Height function, I firstly traverse all nodes in O(n). Next, I can check the all subtree to meet the definition of a balanced tree to answer this question.

code

Remove all ads