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!
- 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.
1. There are four kinds of tree traversals
- 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…