Largest value in each level of a binary tree

user_15345510 0
Viewed 244

Ok so I am working on my algorithm and data structure knowledge and I am trying to find the largest number in each level of a binary tree. I am not sure what is wrong with my logic here.

class Solution
{
    int maxLevel = 0;
    public ArrayList<Integer> largestValues(Node root)
    {
        //code here
        ArrayList<Integer> arr = new ArrayList<>();
        
        checkHeight(root, 1, arr);
        return arr;
    }
    
    
    void checkHeight(Node root, int height, ArrayList<Integer> arr){
        if(root == null){
            return;
        }
        
        if(maxLevel < height){
            if(root.left != null && root.right != null){
                arr.add(Math.max(root.left.data, root.right.data));
            }
            if(root.left != null && root.right == null){
                arr.add(root.left.data);
            }
            if(root.left == null && root.right != null){
                arr.add(root.right.data);
            }
            if(root.left == null && root.right == null){
                return;
            }
            maxLevel = height;
        }
        
        checkHeight(root.left, height + 1, arr);
        checkHeight(root.right, height + 1, arr);
    }
    
}
recursive-datastructures data-structures algorithm java
1 Answers

It appears that you are not familiar with what largest number in each level of a binary tree means. Your current implementation takes the largest of the left and right children of a node and if it only has one child then that child.

A level in a binary tree consists of all the nodes that have the same depth regardless of whether they are immediate children of the same parent or not.

Therefor you algorithm is fundamentally wrong.

There are 2 approaches to solve this problem: DFS and BFS.

BFS is more straight forward, or it appears to me at least. Here's how it goes:

  1. Loop over the nodes level by level (which BFS does by design).
  2. Take the maximum element.
  3. Move to the next level.

DFS works as follows:

  1. Keep a dictionary that maps levels as keys to greatest number in the level as value.
  2. As you dive dfs, keep track of the depth with a parameter to your recursive function.
  3. At each node, update the value of the key for that level if the current node is greater.
  4. At the end convert your dictionary to whatever format you need. Note: It doesn't matter what flavor of DFS you use (inorder, preorder, etc.). Just make sure to visit every node and keep track of the depth.
user_77556650
Related