Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
I have a doubt.. We cannot heapify a tree unless it maintains the structural property right? Then how can we apply heapify
From Wikipedia: A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less...
So, in theory, we could maintain depth of the left and right subtrees in each node. At the root node, we will have the degree of imbalance between the left and right subtrees. If left subtree has more depth, then we move nodes from left to right subtree until the imbalance has been corrected to a difference of <= 1. Perhaps a recursive approach may be useful...
I have not coded this up, but will try now...just thought I will post the idea first.
O(n) method....
- So you had 20 Amazon interviews back to back???? Stop posting your study questions! March 05, 2014