# Binary Tree Cheat Sheet for next Interview

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