1. Intro to Binary trees #

Created Thursday 30 January 2020

• A special kind of tree, i.e each node has at most 2 children. i.e 0(leaf) 1 or 2.

• They are used in many scenarios. In interviews as well.

• How does it impact our TreeNode class?

  1. Children.capacity() <= 2. It is finite.
  2. Hence store them as ‘left’ and ‘right’ nodes addresses.
  3. vector is no longer a requirement.

• To avoid confusion, we have BinaryTreeNode

{ T data; BinaryTreeNode* left, right; }

Note: 1 and 1 /
2 2 are different(bit by bit) here. They are the same even in generic trees. Order did matter there too.

• The problem is that the skewed tree is different because the size of the child structure is fixed to 2. Hence two possibilities are present.

• We have created left and right due to restriction in the system, arbitarirness of left and right, this will be useful later.