oasisferro.blogg.se - How to burn chip with binary editor

HOW TO BURN CHIP WITH BINARY EDITOR HOW TO
HOW TO BURN CHIP WITH BINARY EDITOR FULL

We can also have it return the longest path so far from the starting node, if found, which is simply the sum of the function called on both the left and right children (plus one, for the current node). This can be solved using a recursive function which returns the length of the path from the current node down to the starting node (or just the longest path to any leaf if the starting node isn't below it).

HOW TO BURN CHIP WITH BINARY EDITOR HOW TO

You'll probably find How to find the lowest common ancestor of two nodes in any binary tree? helpful. The number of steps it takes to get from the starting node to the deepest node on the opposite side is (dStart + dOppositeSide).Īnd the number of steps it takes to burn the entire tree is the maximum of those two. The number of steps it takes to get from the starting node to the deepest node on that side of the tree is (dSameSide - dCommonAncestor) + (dStart - dCommonAncestor). You can obtain all that information from a single inorder traversal of the tree.

Depth of the lowest node on the opposite side of the tree, dOppositeSide.

Depth of the lowest common ancestor of the starting node and the node identified in #3.

The depth of the node furthest from the root on the starting node's branch (i.e.

The depth of the starting node (call it dStart).

Whether the starting node is left or right of the root.

It occurs to me that you need the following: So, what search would be helpful here, DFS orīFS? I think having this in mind will guide me towards my solution, but again. From my own understanding, it has to work with all cases.

HOW TO BURN CHIP WITH BINARY EDITOR FULL

But again, I'm not getting the full scope of the tree. The expected output for this example should be 6s (starting from the 0s with the given node). Print ("Starting from the given node, it will take %ds to burn the whole tree" % (maxDiameter())) How_long = max(max(left_diameter, right_diameter), root_diameter) Root_diameter = maxHeight(root.left) + maxHeight(root.right) Return 1 + max(maxHeight(root.left), maxHeight(root.right)) Here is my implementation in Python 3: # Tree class

However, when I implemented my functions, I'm only getting the result of the starting node to the end of the given node without checking the previous parent nodes. My approach was to find the diameter, along with the height of the tree to look for the furthest node to node. I found this cool article and followed it up and implement the idea behind. With the same pattern, the tree will be burned in (s + 7) NĪfter understanding a little bit, I did a small research in figuring out how to do it. Now at the third second (s + 3) will be like this: N Happening in the first second, where seconds is s, so in the zeroth s: 1Īfter one second has passed, the tree will be updated with more burned nodes.Īn example of the next second (s + 1) will be like this: 1Īn example of the next second (s + 2) will be like this: 1 Say you have a tree like this, where N is the node that is on fire. Time(1second to burn from node to node) it takes to entire tree getīurned? The fire will spread to all the paths from a node." "A binary tree is started burning from a leaf node. I got a problem during one of my mock interview where I had to find how long will a binary tree completely burn down after one given node is already on fire.