Recursion in Binary Tree
When we call getSize on a binary tree object
We could use recursive method to solve many type of questions, especially when the question can be boiled down to many little sub-problems. Such as the classic merge sort , quick sort, and reverse linked list problems. You could find out that the logic we use to sort a big array using merge sort is the same as the logic we use for a smaller size array. The logic we reverse a long linked list is the same as the logic we reverse a linked list with only 2 nodes .. etc.
Therefore, when we ever take a look for the binary tree data structure, it is not a surprise that recursive approach will help us to deal with it in a very handy way. For the most cases, we just need to consider a 3 steps approach for a node, which have parent and 2 child nodes. Then apply this logic to every node in the binary tree using recursion. It is both effective and elegant :-)
So here are the 3 steps we need to consider :
Step 1 : What a node want from his left and right child node
Step 2: After receive this value, what this node do at current level
Step 3: Then what this node should return to its parent node
Note: Step 1 and 3 should be the same thing essentially so we used same red color.
-- 1. Check Balance for Binary Tree
Check if a given binary tree is balanced. A balanced binary tree is one in which the depths of every node’s left and right subtree differ by at most 1.
---------------------------------------------------------------------------------------------------------------
According to the definition of a balanced binary tree we could do a height checking for every node's two child node, which will cost O(n*log(n)). We certainly could do better by following the 3 steps pattern above.
I will copy paste that 3 steps and see what we want for each step:
Step 1 : What a node want from his left and right child node
-- We want the height of left subtree and right subtree
Step 2: After receive this value, what this node do at current level
-- We will compare that two value see are we balance at current level
Step 3: Then what this node should return to its parent node
-- If we still balance at current level , keep passing its height to parent, otherwise a special value like -1, will indicate a un-balanced condition.
Then according that 3 steps we come out a O(n) solution:
Could you match the 3 steps with the code above ?
--2 . Maximum Sum Path from One Leaf Node to Another
Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return Integer.MIN_VALUE(Java)/INT_MIN (C++).
Examples
-15
/ \
2 11
/ \
6 14
The maximum path sum is 6 + 11 + 14 = 31.
------------------------------------------------------------------------------------------------------------
We will keep using the 3 steps above to see what we need to do:
Step 1 : What a node want from his left and right child node
-- We want the max path sum from leaf node to its left/right node
Step 2: After receive this value, what this node do at current level
--When we could form a leaf to leaf path at current level, we will see if we could update the global maximum sum by using ( leftSum + rightSum + current.value )
Step 3: Then what this node should return to its parent node
-- return the max path sum from one left node to this node to its parent
Here is the 3 steps in code :
-- 3. Maximum Sum Path from Any Node to Any Node
Given a binary tree in which each node contains an integer number. Find the maximum possible sum from any node to any node (the start node and the end node can be the same).
Assumptions
- The root of the given binary tree is not null
Examples
-1
/ \
2 11
/ \
6 -14
one example of paths could be -14 -> 11 -> -1 -> 2
another example could be the node 11 itself
The maximum path sum in the above binary tree is 6 + 11 + (-1) + 2 = 18
---------------------------------------------------------------------------------------------------------------
We certainly could still using that 3 steps to process this problem, but since we just completed question 2 , we could, then , consider the difference between this 2 question.
Difference 1. We could update the global maximum sum in any level
2. We could not including the left/right sub-result (cause one node value is still valid ).
Therefore here is the code :
I still comment the 3 steps for reference ^^
-- 4. Least Common Ancestor in Binary Tree
Given two nodes in a binary tree, find their lowest common ancestor.
Assumptions
- There is no parent pointer for the nodes in the binary tree
- The given two nodes are guaranteed to be in the binary tree
---------------------------------------------------------------------------------------------------
Compare to previous example, the solution for this problem is not very intuitive at beginning and require some definition knowledge about what is a common ancestor in a binary tree. Here is 2 examples:
5
/ \
9 12
/ \ \
2 3 14
The lowest common ancestor of 2 and 14 is 5
The lowest common ancestor of 2 and 9 is 9
-------------------------
Step 1 : What a node want from his left and right child node
-- We want to know weather the two target node is under their sub-tree
Step 2: After receive this value, what this node do at current level
-- We will combine 2 and 3 steps together, cause according to the two value we get from child node, we will return different value to parent node accordingly
Step 3: Then what this node should return to its parent node
-- if we see both targets appears under right and left subtree, we return current node to indicate current node is the least common ancestor
else if we did not see anything from two child , we return null to tell parent nothing under this node.
else ( we find one node under this node ) we return this founded node value to its parent to indicate this one node is under this current node.
Code is actually very simple :
-- We want to know weather the two target node is under their sub-tree
Step 2: After receive this value, what this node do at current level
-- We will combine 2 and 3 steps together, cause according to the two value we get from child node, we will return different value to parent node accordingly
Step 3: Then what this node should return to its parent node
-- if we see both targets appears under right and left subtree, we return current node to indicate current node is the least common ancestor
else if we did not see anything from two child , we return null to tell parent nothing under this node.
else ( we find one node under this node ) we return this founded node value to its parent to indicate this one node is under this current node.
Code is actually very simple :
Hope you enjoyed this special way to consider a binary tree problem with recursion !
Happy Coding <>
Ye Jiang
No comments:
Post a Comment