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

就活 グラフ理論 binary Tree balanced binary tree

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