2764. is Array a Preorder of Some โ€ŒBinary Tree

MediumStackTreeDepth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem provides us with a 2D integer array, nodes, that we need to analyze to determine if it represents a preorder traversal of a binary tree. Preorder traversal is a method of visiting all the nodes in a tree where we first visit the node itself, then the left subtree, and finally the right subtree, recursively.

Each element of nodes is in the form [id, parentId], where id is the identifier for the current node, and parentId is the identifier for this node's parent. If the node is the root of the tree, it will have a parentId of -1.

A valid preorder traversal is one where nodes are visited exactly in the order they are laid out in nodes. The task is to return true if nodes represents such a valid preorder traversal, otherwise return false.

Intuition

To validate that nodes is the preorder traversal of a binary tree, we can model the traversal process using a Depth-First Search (DFS) approach.

Our main tool is a recursive function dfs(i) that undertakes the traversal process. We use it to traverse nodes as if we're moving through a binary tree in preorder and checking if the nodes array matches this traversal.

Here's the intuition behind each step taken to come up with the solution:

  1. The given sequence's element alignment must simulate entering each node, then delving into its child nodes as encountered in preorder traversal.

  2. Starting from the first node (which we expect to be the root), we aim to traverse its children in the order given in nodes.

  3. We utilize a pointer k to keep track of our position in nodes during traversal.

  4. The graph g represents the tree. In g, we store child nodes under their respective parent nodes. If a node doesn't appear as any node's parent, then it would not exist in g which implies that it's either a leaf or an unconnected node (which would result in false).

  5. For the DFS function dfs(i), we check if the current node index i matches the index nodes[k][0]. If not, this suggests a mismatch in the traversal order, hence the current nodes cannot represent a preorder traversal sequence.

  6. We then increment k by 1 and recursively apply dfs to the children nodes, recorded in g[i].

  7. If the DFS goes through all the nodes successfully with the indexes matching the preorder traversal sequence, and k equals the length of nodes (meaning every node in nodes has been visited in sequence), nodes is a valid preorder traversal sequence.

In summary, the solution employs a graph representation and DFS to simulate and verify the preorder traversal, checking whether nodes correspond to such a traversal for some tree. If the preorder traversal process is completed without mismatches and includes all nodes, we confirm that nodes represents a valid preorder traversal.

Learn more about Stack, Tree, Depth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The solution to this problem leverages depth-first search (DFS) to emulate the preorder traversal of the binary tree that nodes is expected to represent.

Here's a step-by-step walkthrough of how we implement this:

  1. Graph Construction: We initialize an empty graph g using defaultdict(list). This graph maps parent nodes to their child nodes. For each node i with a parent p in nodes, we append i to g[p]. Nodes with parentId of -1 wonโ€™t have any entry in g as they are the roots.

  2. DFS Function (dfs): The recursive function dfs(i) embodies the exploration logic. It's designed to perform the following actions:

    • Check whether the current node index i matches the current node index in nodes[k].
    • If there is a mismatch (i != nodes[k][0]), the function returns False, as the current sequence does not reflect a valid preorder traversal.
    • When a match is found, we increment the global variable k and proceed to recursively apply dfs to each child node listed under g[i] in the graph.

  3. Recursive Traversal: The dfs function attempts to visit all child nodes of the current node i recursively, checking for continuity and consistency with nodes. When dfs visits a new node, it looks for a match at the current index k. The process is repeated until all nodes in the graph g have been visited, or a mismatch is detected.

  4. Validation: After setting up the graph and the dfs function, we begin the traversal with dfs(nodes[0][0]) since we expect the first entry in nodes to represent the root of the binary tree. The traversal only deems valid if two conditions are met post-traversal:

    • The dfs(nodes[0][0]) function should return True, indicating that the traversal completed without detecting any mismatch.
    • The variable k should equal the length of nodes, ensuring that each node was visited exactly once in the correct preorder sequence.

If both conditions are satisfied, we return True, signaling that the nodes array indeed represents the preorder traversal of a binary tree. Otherwise, we return False.

Through this combination of graph data structure and DFS, the solution mirrors the preorder traversal by visiting nodes in the expected sequence and checking for the integrity of the traversal at each step.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's consider a small example to illustrate how the solution approach works. Suppose we are given the following nodes array:

1nodes = [[1, -1], [2, 1], [3, 2], [4, 1]]

This array is supposed to represent a binary tree's preorder traversal. Let's walk through our algorithm to check whether it's valid.

  1. Graph Construction: We begin by constructing our graph g. By iterating through nodes, we populate g as follows:

    • Since nodes[0][1] is -1, node 1 is the root and will not have any parent entry in g.
    • Node 2 is the child of node 1, so we add 2 to g[1].
    • Node 3 is the child of node 2, so we add 3 to g[2].
    • Node 4 is another child of node 1, so we add 4 to g[1].

    The resulting graph g looks like this: {1: [2, 4], 2: [3]}.

  2. DFS Function (dfs): Our dfs function will check the sequence of the nodes. We also have a global pointer k initialized to 0:

  3. Recursive Traversal: We start our traversal with dfs(nodes[0][0]) which is dfs(1). Inside this function:

    • We check if nodes[k][0] is 1. It is, so we continue.
    • We increment k to 1 and apply dfs to g[1], which contains [2, 4].
    • First, we call dfs(2). We check if nodes[k][0] is 2. It is, so we continue.
    • We increment k to 2 and call dfs(3) since 3 is a child of 2.
    • Inside dfs(3), we check if nodes[k][0] is 3. It is, so we continue.
    • We increment k to 3 and since 3 has no child, dfs(3) returns True.
    • We return to dfs(2) and since there are no more children, it returns True.
    • Back in dfs(1), we proceed with the next child in g[1], which is 4.
    • We call dfs(4) and check if nodes[k][0] is 4. It is, so we continue.
    • We increment k to 4, and since node 4 has no children, dfs(4) returns True.
    • Finally, dfs(1) has no more children to process and returns True.

  4. Validation: After the recursive traversal, we check our conditions for a valid preorder traversal:

    • The dfs(nodes[0][0]) function returned True, indicating no mismatches were found.
    • The global counter k is 4, which is equal to the length of nodes, ensuring all nodes were visited in the correct sequence.

Since both conditions are satisfied, we return True. The nodes array [1, -1], [2, 1], [3, 2], [4, 1] does represent a valid preorder traversal of a binary tree.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def isPreorder(self, nodes: List[List[int]]) -> bool:
6        # Helper function for Depth-First Search (DFS)
7        def dfs(current: int) -> bool:
8            nonlocal index
9            # Check if the current node matches the node at the current index
10            if current != nodes[index][0]:
11                return False
12            # Move to the next index in the preorder traversal
13            index += 1
14            # Perform DFS for all child nodes and ensure they match the preorder traversal
15            return all(dfs(child) for child in graph[current])
16
17        # Building an adjacency list to represent the tree
18        graph = defaultdict(list)
19        for node, parent in nodes:
20            graph[parent].append(node)
21      
22        # Index for tracking the current position in the preorder traversal
23        index = 0
24        # Start DFS from the first node and check if the whole list is a valid preorder traversal
25        return dfs(nodes[0][0]) and index == len(nodes)  # Check if all nodes were visited
26
1class Solution {
2    private Map<Integer, List<Integer>> graph = new HashMap<>();
3    private List<List<Integer>> preorderNodes;
4    private int currentIndex;
5
6    // This method checks if the given list of nodes represents a valid preorder traversal
7    // of a binary tree.
8    public boolean isPreorder(List<List<Integer>> nodes) {
9        this.preorderNodes = nodes;
10      
11        // Build a graph representing the tree; the key is the parent node, and the values are the children.
12        for (List<Integer> node : nodes) {
13            graph.computeIfAbsent(node.get(1), k -> new ArrayList<>()).add(node.get(0));
14        }
15      
16        // Perform a DFS starting from the root node (assumed to be at the first position in the list),
17        // and verify if the preorder traversal matches the input list.
18        boolean isValidPreorder = dfs(preorderNodes.get(0).get(0)) && currentIndex == nodes.size();
19      
20        // Reset the index for future calls
21        currentIndex = 0;
22      
23        return isValidPreorder;
24    }
25
26    // Helper method for DFS traversal that checks if the nodes are visited in the given preorder.
27    private boolean dfs(int nodeValue) {
28        // Check if the current node matches the current node in preorderNodes at index currentIndex.
29        if (nodeValue != preorderNodes.get(currentIndex).get(0)) {
30            return false;
31        }
32        currentIndex++;
33
34        // Recursively visit all child nodes.
35        for (int child : graph.getOrDefault(nodeValue, List.of())) {
36            if (!dfs(child)) {
37                return false;
38            }
39        }
40      
41        return true;
42    }
43}
44
1#include <vector>
2#include <unordered_map>
3#include <functional>
4
5class Solution {
6public:
7    // Function to check if the provided nodes array represents a valid preorder traversal
8    bool isPreorder(const std::vector<std::vector<int>>& nodes) {
9        int currentIndex = 0; // Current index to track position in preorder traversal
10        std::unordered_map<int, std::vector<int>> graph; // Adjacency list representation of the graph
11
12        // Build the graph with child to parent relationships
13        for (const auto& node : nodes) {
14            graph[node[1]].push_back(node[0]);
15        }
16
17        // Define the DFS function using lambda syntax, capturing the currentIndex by reference
18        std::function<bool(int)> deepFirstSearch = [&](int nodeValue) {
19            // Check if the current node value matches with the expected value from preorder traversal
20            if (nodeValue != nodes[currentIndex][0]) {
21                return false;
22            }
23            ++currentIndex; // Move to the next index in preorder traversal
24
25            // Recursively visit all children of the current node
26            for (int childValue : graph[nodeValue]) {
27                if (!deepFirstSearch(childValue)) {
28                    return false;
29                }
30            }
31            return true;
32        };
33
34        // Start DFS from the root node (the first node in the given preorder traversal)
35        // and check if we have visited all nodes exactly once
36        return deepFirstSearch(nodes[0][0]) && currentIndex == nodes.size();
37    }
38};
39
1// Function to determine if the given list of nodes represents a preorder traversal of a tree.
2function isPreorder(nodes: number[][]): boolean {
3    let currentIndex = 0; // Track the current index of nodes to match with preorder
4    const graph: Map<number, number[]> = new Map(); // Map to hold the adjacency list representation of the tree
5
6    // Construct the graph from the node pairs
7    for (const [node, parent] of nodes) {
8        if (!graph.has(parent)) {
9            graph.set(parent, []);
10        }
11        graph.get(parent)!.push(node);
12    }
13
14    // Helper function to perform DFS and verify the preorder sequence
15    const depthFirstSearch = (node: number): boolean => {
16        // If current node isn't the expected node in the preorder sequence, return false.
17        if (node !== nodes[currentIndex][0]) {
18            return false;
19        }
20        currentIndex++; // Move to the next index in the preorder sequence
21
22        // Traverse all children nodes recursively
23        for (const childNode of graph.get(node) ?? []) {
24            if (!depthFirstSearch(childNode)) {
25                return false; // If any child's preorder check fails, return false immediately
26            }
27        }
28        return true; // If all children are traversed in preorder, return true
29    };
30
31    // Start DFS from the root node (it's assumed that the root node is at the first index of nodes)
32    return depthFirstSearch(nodes[0][0]) && currentIndex === nodes.length; // Check preorder traversal is complete
33}
34
Not Sure What to Study? Take the 2-min Quiz๏ผš

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the nodes list. This is because the algorithm visits each node exactly once due to the dfs traversal, and the k index ensures that we do not revisit nodes. Each call to dfs increments k once and since there are n nodes, we get a linear time complexity.

The space complexity is also O(n). The space is used by the g dictionary, which stores a list of children for each node, and the recursive call stack of the dfs function. In the worst case, if the tree is completely unbalanced, the depth of the recursion can be n, which would mean n function calls on the call stack. Every node also appears in the dictionary, thus, the space complexity is proportional to the number of nodes, giving us O(n) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ