# LintCode: Binary Tree Maximum Node

Binary Tree Maximum Node

Similar Problems:

```Follow-up:
- Assume we can't use global variable
- I want to return all max nodes
- I want to return the last max node
- I want to return the second max node, if we have. Otherwise return the first max node
```

Description

Find the maximum node in a binary tree, return the node.

Example

```Given a binary tree:

1
/   \
-5     2
/ \   /  \
0   3 -4  -5
return the node with value 3.
```

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.

• Solution: With sub-function
```## Blog link: https://code.dennyzhang.com/binary-tree-maximum-node
## Basic Ideas: any tree traversal
## Here we use pre-order
## Complexity: Time O(n), Space O(h)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of tree
@return: the max node
"""
def maxNode(self, root):
def dfs(root, maxNode):
if root is None: return maxNode
if root.val > maxNode.val: maxNode = root
maxNode = dfs(root.left, maxNode)
maxNode = dfs(root.right, maxNode)
return maxNode
return dfs(root, root)
```

• Solution: Without sub-function
```## Blog link: https://code.dennyzhang.com/binary-tree-maximum-node
## Basic Ideas: any tree traversal
## Here we use pre-order
## Complexity: Time O(n), Space O(h)
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param: root: the root of tree
@return: the max node
"""
def maxNode(self, root):
if root is None: return root

res = root
if root.left:
p = self.maxNode(root.left)
if p.val > res.val: res = p

if root.right:
p = self.maxNode(root.right)
if p.val > res.val: res = p
return res
```

Share It, If You Like It.