We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Nop, because it's really a graph, and thus each node (in case it was a binary tree) may have 3 "children" since there's no direction in the relation between nodes.
You must understand tree in graph sens: an undirected acyclic connected graph (no cycle, a single connected component and exactly order-1 edges).
The only relevant information you can get from the fact that we got a tree is that there's no cycle. This has two consequences: cutting one edge break connectivity and in a DFS traversal you don't need to mark vertices, just remember the parent of the current vertex.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the Tree
You are viewing a single comment's thread. Return to all comments →
Nop, because it's really a graph, and thus each node (in case it was a binary tree) may have 3 "children" since there's no direction in the relation between nodes.
You must understand tree in graph sens: an undirected acyclic connected graph (no cycle, a single connected component and exactly order-1 edges).
The only relevant information you can get from the fact that we got a tree is that there's no cycle. This has two consequences: cutting one edge break connectivity and in a DFS traversal you don't need to mark vertices, just remember the parent of the current vertex.