Longest Univalue Path

I have a childhood best friend which we both attended K-12 in the same sequence of schools. We used to hang out on weekends and in some occasions would go out with the family. After high school we both went in different directions. We lost track of each other while attending college. A few years went by and we reconnected. Since then we have visited in person and our spouses appear to have connected well.

Through the years we kept in touch about once a month via Skype. Since the COVID-19 pandemic started, we talk once a week, typically on Friday. We are both morning people so we set the call time between 06:00 AM and 07:00 AM. This morning around 05:00 AM I received a message via Gmail that he had some work appointments early morning. We skipped the call but will reconnect next week.

In our daily professional lives, depending on what we do, we may or may not encounter problems that are simpler to code and more elegant to solve using recursion. On occasions I have posted the recursive and the equivalent iterative algorithm. Note that all recursive algorithms make heavy use of stack memory. Also they tend to perform slower than their iterative counterparts. In this post I will not touch on both implementations nor time them.

The problem at hand is 687. Longest Univalue Path by LeetCode. By the way, according to OneLook.com the word “univalue” is not proper English. If interested in this problem please take a look at the description on the LeetCode web site.

We are given a binary tree (BT) (not a binary search tree (BST)) and we are supposed to write some code to determine the number of edges between adjacent nodes sharing the same value. The site provides two examples. Like I mentioned, if you are interested you can take a look at the BT diagrams that describe the problem.

The diagram for the first BT follows:

The diagram for the second BT follows:

On the first BT we can determine that there are 3 nodes with value 5 so the result should be 2. Look at all other combinations to make sure we agree.

On the second BT, there are 3 adjacent nodes with value 4. The results should also be 2. Please check at the other combinations of paths to make sure we agree on the suggested answer.

I guess that was the easy part. Now we need to write some code that will produce the desired results and will be accepted by LeetCode. I decided to work the problem using Java and the VSCode IDE on a Windows 10 machine. Of course you can use any of the supported programming languages by LeetCode, use their IDE, or use the IDE of choice on your computer. As you know I prefer to work on my machines using the tools I am accustom to. It is different when you are at work (in person or nowadays remotely). In such conditions chances are that you are using the programming languages and tools provided by your employer.

As you know, LeetCode provides the test scaffolding for this problem. If you are like me and prefer to develop and test as much as possible on your machine using the tools you are accustomed to, you will require generating the test scaffolding. Takes longer but in addition to solving the problem you are also learning things you will encounter generating the test cases.

The data is presented in level order and we need to populate a BT. Note that in both examples at the second level node with value 5, the left child is null. As far as I can tell we can ignore the situation for the provided test cases, but if you wish to run additional tests as I did, make sure the BTs are being properly populated.

LeetCode provides the article What does [1,null,2,3] mean in binary tree representation? The article describes how to properly populate the BT in level order. That said; I was not able to locate the associated code. If you do, please let me know to compare what I have in this post.

We will start by displaying the results of multiple runs that I used to build the proper BT and the solution for the problem at hand.

4 2 6 1 3 5 7

main <<< levelOrder: 4 2 6 1 3 5 7
main <<<    inOrder: 1 2 3 4 5 6 7
main <<< longestUnivaluePath: 0


1 2 5 3 6 4

main <<< levelOrder: 1 2 5 3 6 4
main <<<    inOrder: 3 2 6 1 4 5
main <<< longestUnivaluePath: 0


2 7 2 1 1 null 2

main <<< levelOrder: 2 7 2 1 1 2
main <<<    inOrder: 1 7 1 2 2 2
main <<< longestUnivaluePath: 2


4 4 4 4 9 null 5

main <<< levelOrder: 4 4 4 4 9 5
main <<<    inOrder: 4 4 9 4 4 5
main <<< longestUnivaluePath: 3


10 20 30 40 50 60 70

main <<< levelOrder: 10 20 30 40 50 60 70
main <<<    inOrder: 40 20 50 10 60 30 70
main <<< longestUnivaluePath: 0


1 null 2 3

main <<< levelOrder: 1 2 3
main <<<    inOrder: 1 3 2
main <<< longestUnivaluePath: 0


1 null 2 null 3

main <<< levelOrder: 1 2 3
main <<<    inOrder: 1 2 3
main <<< longestUnivaluePath: 0


Example 1:

5 4 5 1 1 null 5

main <<< levelOrder: 5 4 5 1 1 5
main <<<    inOrder: 1 4 1 5 5 5
main <<< longestUnivaluePath: 2


Example 2:

1 4 5 4 4 null 5

main <<< levelOrder: 1 4 5 4 4 5 
main <<<    inOrder: 4 4 4 1 5 5 
main <<< longestUnivaluePath: 2

Each test case comprises of a line of text with integers and occasional ‘null’ values. Note that the first value represents the value for the root node. The next two values are for the nodes in the BT al level 2. The next four values are for the nodes at level tree (if needed). A null node in the sequence represents a missing child node on the previous level.

The test scaffolding displays the BT using an inOrder traversal followed by the breadth first or level order traversal. I did both to possibly get a better picture of the BT to make sure things were going well before working on the actual problem.

The following line displays the result of the problem at hand. In the first case, if you fill the BT in the order provided, you should agree with the answer generated by the code.

The third example generated a BT with 3 levels. The right side of the BT on all levels has value 2. The answer for this BT is 2. If you disagree please let me know.

The last two examples represent the examples provided by LeetCode. You can see that we use the ‘null’ string to skip in both cases the left child of the node with value 5 in the second level of the BT.

/**
 * Definition for a BT node.
 */
class TreeNode {

    // **** members ****
    int         val;
    TreeNode    left;
    TreeNode    right;
    
    // **** constructors ****
    TreeNode() {
    }

    TreeNode(int val) {
        this.val    = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val    = val;
        this.left   = left;
        this.right  = right;
    }
	
	@Override
    public String toString() {
        return "val: " + this.val + " left: " + this.left + " right: " + this.right;
    }
}

The description of the nodes for the BT is provided by LeetCode. Each node has a value and two children. There are 3 constructors at our disposal.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {

        // **** BT root ****
        TreeNode root = null;

        // **** open scanner ****
        Scanner sc = new Scanner(System.in);
        
        // **** read the values for the nodes in the BT ****
        String[] arr = sc.nextLine().split(" ");

        // **** populate the BT in level order (supports 'null' values) ****
        root = populateTree(arr);

        // ???? level order traversal (check the BT) ????
        System.out.print("main <<< levelOrder: ");
        levelOrder(root);
        System.out.println();

        // ???? inorder traversal (check the BT) ????
        System.out.print("main <<<    inOrder: ");
        inOrder(root);
        System.out.println();

        // **** close scanner ****
        sc.close();

        // **** compute and display the result ****
        System.out.println("main <<< longestUnivaluePath: " + longestUnivaluePath(root));
    }

Once again, the test scaffolding is not required to solve this problem. LeetCode provides one. This code shows the one I generated to develop the code on my machine with the tools I commonly use for Java.

We start by declaring an empty BT and opening the scanner to read the line with the values for the BT. We read the line and split each value into a String array to accommodate the ‘null’ string. We then populate the BT. We then display the BT using an inOrder and a breadth first search or level order. This is done to check that the BT was properly built. Since we are done processing input, we close the scanner. We could have closed it after the call to the function populateTree() was made. It is good practice to allocate and release objects immediately before they are needed and after they are done using. In this simple example it makes no difference.

The final line is the function that we need to implement as part of the problem. It generates and displays the result. Note that the display is only part of the test scaffolding.

    /**
     * This recursive function inserts nodes in level order into a BT.
     * This method does not support 'null' nodes.
     * 
     * !!!This method is NOT used by this solution !!!
     */
    static TreeNode insertLevelNode(String[] arr, TreeNode root, int i) {

        // **** recursion base case ****
        if (i < arr.length) {
            
            // **** allocate element (if needed) ****
            if (!arr[i].equals("null")) {
                TreeNode temp = new TreeNode(Integer.parseInt(arr[i]));
                root = temp;
            } else {
                return null;
            }
    
            // **** insert left child ****
            root.left = insertLevelNode(arr, root.left, 2 * i + 1);
    
            // **** insert right child ****
            root.right = insertLevelNode(arr, root.right, 2 * i + 2);
        }
    
        // **** ****
        return root;
    }

This last code is not used at all. I left it because it is able to load a BT in level mode, but it will not handle ‘null’ strings. I spent some time getting it to work and at some point decided to start from scratch. I just left it in when I was about to delete it from the code base. Note that in production, it is good practice to remove functions, methods and variables that are not used.

    /**
     * Enumerate which child in the node at the head of the queue 
     * should be updated.
     */
    enum Child {
        LEFT,
        RIGHT
    }

This enumeration is used to determine which child (left or right) the next node should be attached to the head node in an auxiliary queue. This will become cleared when we look at the code that populates the BT.

    /**
     * Traverse the specified BT displaying the values in order.
     * This method is used to verify that the BT was properly populated.
     */
    static void inOrder(TreeNode root) {

        // **** end condition ****
        if (root == null)
            return;

        // **** visit the left sub tree ****
        inOrder(root.left);

        // **** display the value of this node ****
        System.out.print(root.val + " ");

        // **** visit the right sub tree ****
        inOrder(root.right);
    }

This is a recursive method used to display the values of the BT during an in order traversal. We will use it to check if things are working well when populating the BT.

    /**
     * Display the specified BT in level order.
     * This method is used to verify that the BT was properly populated.
     */
    static void levelOrder(TreeNode root) { 

        // **** end condition ****
        if (root == null) 
            return; 

        Queue<TreeNode> q = new LinkedList<TreeNode>();

        // **** to start the process ****
        q.add(root);
        
        // **** loop displaying a tree level ****
        while (!q.isEmpty()) { 

            // **** ****
            System.out.print(q.peek().val + " ");

            // **** ****
            if (q.peek().left != null) 
                q.add(q.peek().left);

            // **** ****
            if (q.peek().right != null) 
                q.add(q.peek().right);

            // **** ****
            q.remove();
        }
    } 

This method is used to traverse in a level order the BT. This method will be used to check if the BT is populated correctly.

    /**
     * This method populates a BT in level order as specified by the array.
     */
    static TreeNode populateTree(String[] arr) {

        // **** root for the BT ****
        TreeNode root = null;

        // **** ****
        Queue<TreeNode> q = new LinkedList<TreeNode>();

        // **** traverse the array of values inserting the nodes into the BT ****
        for (String strVal : arr)
            root = insertValue(root, strVal, q);

        // **** clear the queue ****
        q = null;

        // **** return the root of the BT ****
        return root;
    }

This is an iterative approach to populate a BT in level order. We provide an array of strings with the integer values and the ‘null’ string to skip populating null children.

We start with tree representation, a queue and then traverse the array inserting new nodes with values from the array. When done we clear the queue (not needed) and return the complete BT.

    // **** child turn to insert on node at head of queue ****
    static Child  insertChild = Child.LEFT;

    /**
     * This method inserts the next value into the specified BT.
     * This method is called repeatedly from the populateTree method.
     */
    static TreeNode insertValue(TreeNode root, String strVal, Queue<TreeNode> q) {

        // **** node to add to the BT in this pass ****
        TreeNode node = null;

        // **** create a node (if needed) ****
        if (!strVal.equals("null"))
            node = new TreeNode(Integer.parseInt(strVal));

        // **** BT is empty (this is the root node) ****
        if (root == null)
            root = node;

        // **** add node to left child (if possible) ****
        else if (insertChild == Child.LEFT) {
        
            // **** add this node as the left child ****
            if (node != null)
                q.peek().left = node; 
            
            // **** for next pass ****
            insertChild = Child.RIGHT;
         }

        // **** add node to right child (if possible) ****
        else if (insertChild == Child.RIGHT) {
        
            // **** add this node as a right child ****
            if (node != null)
                q.peek().right = node;

            // **** remove node from queue ****
            q.remove();

            // **** for next pass ****
            insertChild = Child.LEFT;
        }

        // **** add this node to the queue (if needed) ****
        if (node != null)
            q.add(node);
        
        // **** return the root of the BT ****
        return root;
    }

We start by creating a new node with the specified integer value if the string in not ‘null’. We then check three conditions.

If the BT is empty, we assign the node as the root. The tree is being populated in order by level. We check if we need to set the left node child of the head node in the auxiliary queue. If the node is not null we set it as the left child. We then update the insertChild to process the right child on the next pass. If we need to insert the right child on the head node in the auxiliary queue, we do so if the node is not null. At this point we are done with the head node because we have processed the left and the right children. We update the insertChild variable to process the left child on the next head node in the queue on the next pass.

We then check if the node is not null and add it to the queue. A node labeled ‘null’ would be skipped so the left or right child would not be populated by the current node.

    // **** must be outside of the recursive method ****
    static int maxPath = 0;


    /**
     * Given a binary tree, find the length of the longest path where each 
     * node in the path has the same value. This path may or may not pass 
     * through the root.
     */
    static int longestUnivaluePath(TreeNode root) {

        // **** initialize value ****
        maxPath = 0;

        // **** recursive call ****
        lup(root);

        // **** return value ****
        return maxPath;
    }

The maxPath variable will be used to track the maximum path of edges between nodes with the same value. We need to keep this value out of the recursive call because we will use its value on each recursive pass.

The longestUnivaluePath function initializes the maxPath variable, calls the recursive call lup() which determines the value of the maxPath, and when done returns the value as specified by the requirements.

    /**
     * Given a binary tree, find the length of the longest path where each 
     * node in the path has the same value. This path may or may not pass 
     * through the root.
     * This is a recursive function.
     * Time complexity: O(n)
     */
    static int lup(TreeNode root) {

        // **** base case ***
        if (root == null)
            return 0;

        // **** process the left tree ****
        int leftLen = lup(root.left);

        // **** process the right tree ****
        int rightLen = lup(root.right);

        // **** store the maximum child lengths ****
        int leftMax = 0;
        int rightMax = 0;

        // **** ****
        if ((root.left != null) &&
            (root.left.val == root.val))
            leftMax += leftLen + 1;

        // **** ****
        if ((root.right != null) &&
            (root.right.val == root.val))
            rightMax += rightLen + 1;

        // **** update the maxPath ****
        maxPath = Math.max(maxPath, leftMax + rightMax);

        // **** return the max length ****
        return Math.max(leftMax, rightMax);
    }

OK gals and guys, this is the core of the function that needs to address finding the longest univalue path. Note that for the LeetCode problem we will need the definition of the maxPath variable and the last two functions.

We check the base case. We return 0 because a null child does not contribute to the path value. We then process the left and right trees. This will provide the counts of the children.

We need a running value which is stored in the next two variables.

We now update the left and right max values taking into account the value or the root node we are currently visiting.

Now we are ready to update the external maxPath value.

To continue the recursive process we return the max value of the children of the current root node.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 1,648 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.