Binary Tree Cheat Sheet for next Interview

binary tree

A binary Tree is a tree-like data structure where every node has at most two children.

If you flip the tree upside down, it kind of looks like a tree. That’s where the name comes from!

Definitions

• Node — a data structure consisting of a value, together with left and right references to other nodes.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):   
       self.val = val         
       self.left = left  
       self.right = right

• Root — the top node without a parent
• Edge — the connection between two nodes
• Leaf — a node without any children

How to recognize the leaf node in code?

if not node.left and not node.right  

• Depth — the number of edges from the tree’s root node to the current node. That means the root node will have a depth of 0

• Height — the number of edges on the longest path from the node to a leaf. That means a leaf node will have a height of 0

• Diameter: The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Useful Takeaway

1. There are four kinds of tree traversals

traversal demonstration

• Pre-order: We walk the graph, from the top going counter-clockwise. Shout every time we pass the LEFT of a node.
• In-order: We walk the graph, from the top going counter-clockwise. Shout every time when you cross the BOTTOM of a node.
• post-order: We walk the graph, from the top going counter-clockwise. Shout every time when…