Count median in binary tree

Question

Given a binary tree, write a function to calculate the median of the values stored in the nodes. The median is defined as the middle value when the values are sorted in ascending order; if there is an even number of values, return the average of the two middle values. Your function should take the root of the binary tree as input and return the median as a float.

Codemia · Accepted Answer

To find the median of values in a binary tree, we need to consider the properties of both binary trees and the definition of median. The binary tree can contain an arbitrary number of nodes, which means we cannot directly access elements by index. We will use an in-order traversal method, which visits nodes in sorted order for binary search trees, but it will also work for general binary trees since we can collect all values into a list. This method fits well as we will simultaneously traverse the tree and collect values. The median can be calculated after sorting this list of node values.

1. **In-Order Traversal**: We will use depth-first search (DFS) through in-order traversal to collect all node values into a list. 
2. **Sorting the Values**: After obtaining the list of values, we will sort this list. 
3. **Calculating the Median**: If the list has an odd length, the median is the middle element. If even, it is the average of the two middle values.

**Example**: For a binary tree with the structure: 
```
       5
      / \
     3   8
    / \   \
   1   4   9
```
The in-order traversal yields the values: [1, 3, 4, 5, 8, 9]. This list is already sorted. Since there are 6 values (even), the median will be (4 + 5) / 2 = 4.5.

Here is the Python implementation of the approach:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMedian(root):
    values = []
    def inOrderTraversal(node):
        if not node:
            return
        inOrderTraversal(node.left)
        values.append(node.val)
        inOrderTraversal(node.right)

inOrderTraversal(root)
    values.sort()
    n = len(values)
    if n % 2 == 1:
        return float(values[n // 2])
    else:
        return (values[n // 2 - 1] + values[n // 2]) / 2.0
```
This code defines a TreeNode structure, performs in-order traversal to collect values, sorts them, and computes the median.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of nodes in the binary tree. The in-order traversal itself is O(n). Therefore, the dominant factor is the sorting step. The space complexity is O(n) as we store all node values in a list before calculating the median.

1. **Empty Tree**: If the tree is empty (root is None), we can return None or raise an exception since there are no values to calculate a median. 
2. **Single Node Tree**: If there is only one node, the median is simply the value of that node. 
3. **All Nodes with the Same Value**: If all nodes have the same value, the median will be that value regardless of the number of nodes, demonstrating that the solution handles uniform distributions correctly.

Count median in binary tree

DoorDash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

DoorDash Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string