Post

Data Structures - Basic 1 - Tree

Posted Updated
By Grace L
101 min read
  • ref
    • https://www.geeksforgeeks.org/binary-tree-data-structure/
    • DS - pythonds3 - 7. Binary Tree
    • Data Structures and Algorithms in Java, 6th Edition.pdf

Data Structures - Basic 1 - Data Structures Tree

Type

  • Binary Search Tree(BST)：
    • 在某些資料經常要增加、刪除的應用中，BST常用來做搜尋，
    • 例如許多程式語言的Library中的map和set。
  • Binary Space Partition：
    • 應用於幾乎所有的3D電玩遊戲以決定哪些物件需要rendered。
  • Binary Tries：
    • 應用於大多數high-bandwidth router(高頻寬路由器)以儲存router-tables。
  • Heaps：
    • 用以實現高效率的priority queues(優先權佇列)
    • 許多作業系統用來安排工作程序。
  • Huffman Coding Tree：
    • 例如.jpeg、.mp3等壓縮技術皆使用Huffman編碼。
    • (在一顆20MB的硬碟要價新台幣一萬元的時代，壓縮技術就是救世主。)

Prefix tree, Trie

  • sometimes called a radix or prefix tree
  • a kind of search tree that is used to store a dynamic set or associative array where the keys are usually Strings
  • No node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated.
  • All the descendants of a node have a common prefix of the String associated with that node, and the root is associated with the empty String.

radix-tree

Binary indexed tree, Fenwick Tree

  • sometimes called a binary indexed tree,

  • is a tree in concept, but in practice is implemented as an implicit data structure using an array.

  • Given an index in the array representing a vertex
    • the index of a vertex's parent or child is calculated through bitwise operations 按位运算 on the binary representation of its index.
    • Each element of the array contains the pre-calculated sum of a range of values,
    • and by combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated

  • a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

  • Time Complexity:
    • Range Sum: O(log(n))
    • Update: O(log(n))

Screen Shot 2021-10-25 at 5.34.40 PM

Segment Tree

  • a tree data structure for storing intervals/segments.
  • It allows querying which of the stored segments contain a given point.

Time Complexity

  • Range Query: O(log(n))
  • Update: O(log(n))

segmentTree

Heap

  • a specialized tree based structure data structure that satisfies the heap property:
    • if A is a parent node of B,
    • then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the entire heap.
  • A heap can be classified further as either a “max heap” or a “min heap”.
    • In a max heap,
      • the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node.
    • In a min heap,
      • the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node

Time Complexity:

  • Access Max / Min: O(1)
  • Insert: O(log(n))
  • Remove Max / Min: O(log(n))

heap

basic

The difference between a tree in nature and a tree in computer science a tree data structure has its root at the top and its leaves on the bottom.

若熟悉Linked List(連結串列)將會更容易理解樹：

  • Linked list是 一維的線性結構(不是往前、就是往後)
  • 樹(與Graph)則推廣成多維的結構。

linkedlist

f1

  • A、B、C、D稱為node(節點)，用以代表資料(data)、狀態(state)。
  • 連結各個node之間的連結(link)稱為edge，可能是單方向，或者雙向。

Screen Shot 2021-09-30 at 10.40.39 PM

A Tree is an undirected, connected, acyclic graph

  • 无向的、连通的、无环图

  • the most important nonlinear data structures
  • an organizational relationship that is richer than the simple “before” and “after” relationships between objects in sequences.

properties

properties of trees

Tree(樹)

  • 由一個或多個節點所組成的有限集合，
  • 並且滿足：
    • 存在且只有一個稱為root(樹根)的節點；
    • 其餘的節點可以分割成任意正整數個(包含零個)互斥(disjoint)的集合：T1、…、Tn，其中每一個集合也都滿足樹的定義，這些集合又稱為這棵樹的subtree(子樹)。
    • Tree(樹)是由一個或多個nodes/vertices以及edge所組成，而且沒有cycle的集合(set)。
  • 在樹的結構裡，只有一個root(樹根)，並且不存在cycle。
  • 此特徵將衍生出另外兩項等價的性質：
    • 在樹中若要從root尋找特定node，一定只存在一條路徑(path)。
    • 每個node只會有一個parent。

Forest(樹林)

  • 由n≥0棵彼此互斥(disjoint)的Tree(樹)所形成的集合(Set)，即稱為Forest(樹林)。
  • Forest(樹林)由多個Tree(樹)所組成，可以用來表示互斥集合(disjoint set)。

Trees provide a natural organization for data, and consequently have become ubiquitous structures in

  • file systems,
  • graphical user interfaces,
  • databases, websites,
  • and many other computer systems.

Main applications of trees include:

  1. Manipulate hierarchical data.
  2. Make information easy to search (see tree traversal).
  3. Manipulate sorted lists of data.
  4. As a workflow for compositing digital images for visual effects.
  5. Router algorithms

  6. Form of a multi-stage decision-making (see business chess).

  7. A tree is an abstract data type that stores elements hierarchically. With the exception of the top element, each element in a tree has a parent element and zero or more children elements.
  8. to store information that naturally forms a hierarchy.
  9. Trees provide moderate access/search (quicker than Linked List and slower than arrays).
  10. Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists).
  11. Like Linked Lists and unlike Arrays
    1. Trees dont have an upper limit on number of nodes as nodes are linked using pointers.

define a tree T as a set of nodes storing elements such that the nodes have a parent-child relationship that satisfies the following properties:

  • If T is nonempty, it has a special node, called the root of T, that has no parent.
  • Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.
  • a tree can be empty, meaning that it does not have any nodes.
  • Two nodes that are children of the same parent are siblings.
  • A node v is external if v has no children.
    • External nodes are also known as leaves.
  • A node v is internal if it has one or more children.
  1. 用以描述具有階層結構(hierarchical structure)的問題的首選，
    • 階層結構意味著明確的先後次序，
    • 例如，若要印出ABC三個字母的所有排列組合(permutation)
    • trees are structured in layers
      • the more general things near the top
      • and the more specific things near the bottom.
  2. all of the children of one node are independent of the children of another node.
    • we can change the node without affecting other child node.
  3. each leaf node is unique.
    • can follow a path from the root to any directory.
    • That path will uniquely identify that subdirectory (and all the files in it).
  4. can move entire sections of a tree (called a subtree) to a different position in the tree without affecting the lower levels of the hierarchy.
    • derived from their hierarchical nature
  5. Edges and Paths in Trees
    • An edge of tree T is a pair of nodes (u,v)
    • u is the parent of v, or vice versa.
    • A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge.

Ordered Trees

A tree is ordered if there is a meaningful linear order among the children of each node;

  • purposefully identify the children of a node as being the first, second, third, and so on.
  • Such an order is usually visualized by arranging siblings left to right, according to their order.

Properties or Binary tree

  1. The maximum number of nodes at level l: 2^l
    • level is number of nodes on path from root to the node (including root and node).
    • Level of root is 0, number of nodes = 2^0 = 1
  2. Maximum number of nodes in a binary tree of height h: 2^h – 1.
    • height of a tree is maximum number of nodes on root to leaf path.
    • Height of a tree with single node is considered as 1.
    • In some books, height of the root is considered as 0. In this convention, the above formula becomes 2h+1 – 1
  3. In a Binary Tree with N nodes, minimum possible height or minimum number of levels: Log2(N+1)
    • This can be directly derived from point 2 above.
    • If we consider the height of a leaf node is considered as 0, then above formula for minimum possible height becomes ? Log2(N+1) ? – 1

  4. A Binary Tree with L leaves has at least: Log2L ? + 1 levels A Binary tree has maximum number of leaves (and minimum number of levels) when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.

    L <= 2l-1 [From Point 1] l = ? Log2L ? + 1 where l is the minimum number of levels.

5) In Binary tree where every node has 0 or 2 children, number of leaf nodes is always one more than nodes with two children.

樹的元素

針對node / vertex：

f9

  • degree(分歧度)：
    • 一個node擁有的subtree(子樹)的個數。
    • A的degree為3，F的degree為2，N的degree為0。
  • root(樹根)：
    • 樹中最上層的node，也是唯一一個其parent為NULL的node。
    • A即為root。
  • external node/leaf：
    • 沒有child/subtree的node。
    • G、H、J、K、L、M、N皆為leaf node。
  • internal node：
    • 至少有一個child的node。
    • A、B、C、D、E、F、I皆為internal node。
  • parent <--> child：
    • 以pointer說明，被指向者(pointed)為child，指向者(point to)為parent。
  • siblings：擁有相同parent的node們，互相稱兄道弟。
    • B、C、D共同的parent為A，B、C、D即為彼此的sibling。
  • descendant(子嗣)：
    • 站在A，所有能夠以「parent指向child」的方式找到的node，皆稱為A的descendant，因此整棵樹除了A以外皆為A的descendant。
    • 在F，能夠以「parent指向child」找到的node有L、M，則稱L、M為F的descendant。
  • ancestor(祖先)：
    • 圖四中，站在K，所有能夠以「尋找parent」的方式找到的node，皆稱為K的ancestor，因此，E、B、A皆為K的ancestor。
  • path(路徑)：
    • 由descendant與ancestor關係連結成的edge，例如A-B-E-K、A-C-F-N。
  • level： root-2-3-4
    • 定義root的level為1，其餘node的level為其parent的level加一。
  • height of node：
    • 某一node與其最長path上之descendant leaf node之間的edge數。
    • 例如，F的height為1，D的height為2，leaf node的height為0。
  • height of tree：樹的height即為root的height。
    • 樹的height為A的height，等於3。
  • depth：
    • 某一node與root之間的edge數。
    • 例如，F的depth為2，L的depth為3。

在樹中的traversal(尋訪)之時間複雜度(time complexity)會與height(樹高)有關。

集合關係

Tree(樹)位居承先啟後的重要戰略位置，資料結構之集合關係圖：

f11

本篇介紹的Tree(樹)並沒有限制child/ subtree的個數

  • 理論上可以有多到超過記憶體空間的child node。
    • f1-1
  • 然而在實務上，較常使用每個node至多只有兩個child的樹，為Binary Tree(二元樹)。
    • f2
    • 樹上的每一個node之degree皆為2
    • 並稱兩個child pointer為left child和right child。
  • 從Binary Tree再增加「鍵值(Key)大小規則」，即Binary Search Tree(BST，二元搜尋樹)。
  • 以BST為基礎，在每個node上添加顏色(紅與黑)用以平衡樹的height，以減短搜尋時間，這種樹稱為Red Black Tree(RBT，紅黑樹)。
  • 常見的平衡樹(balanced tree)還有：AVL tree、2-3-4 tree、Splay tree等等，請參考：Wikipedia：Self-balancing binary search tree
  • 另一個方向，若打破「不能存在cycle」的限制，則從Tree推廣至圖(Graph)。

Tree Interface

Tree Abstract Data Type

  • define a tree ADT using the concept of a position as an abstraction for a node of a tree.
  • An element is stored at each position,
  • and positions satisfy parent-child relationships that define the tree structure.

A position object for a tree supports the method:

  • getElement(): Returns the element stored at this position.

accessor methods, allowing a user to navigate the various positions of a tree T :

  • root(): Returns the position of the root of the tree (or null if empty).

  • parent(p): Returns the position of the parent of position p (or null if p is the root).

  • children(p): Returns an iterable collection containing the children of position p (if any).

  • numChildren(p): Returns the number of children of position p.

query methods:

  • isInternal(p): Returns true if position p has at least one child.
  • isExternal(p): Returns true if position p does not have any children.
  • isRoot(p): Returns true if position p is the root of the tree.

general methods, unrelated to the specific structure of the tree. These incude:

  • size(): Returns the number of positions (and hence elements) that are contained in the tree.

  • isEmpty(): Returns true if the tree does not contain any positions (and thus no elements).

  • iterator(): Returns an iterator for all elements in the tree (so that the tree itself is Iterable).

  • positions(): Returns an iterable collection of all positions of the tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public interface Tree<E> extends Iterable<E> {
    Position<E> root();
    Position<E> parent(Position<E> p) throws IllegalStateException;
    Iterable<Position<E>> children(Position<E> p) throws IllegalStateException;

    int numChildren(Position<E> p) throws IllegalStateException;
    boolean isInternal(Position<E> p) throws IllegalStateException;
    boolean isExternal(Position<E> p) throws IllegalStateException;
    boolean isRoot(Position<E> p) throws IllegalStateException;

    int size();
    boolean isEmpty();

    Iterator<E> iterator();
    Iterable<Position<E>> positions();
}

AbstractTree class

  • define an AbstractTree base class,
  • demonstrating how many tree-based algorithms can be described independently of the low-level representation of a tree data structure.
  • In fact, if a concrete implementation provides three fundamental methods—root(), parent(p), and children(p)— all other behaviors of the Tree interface can be derived within the AbstractTree base class.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// /∗∗ An abstract base class providing some functionality of the Tree interface. ∗/
public abstract class AbstractTree<E> implements Tree<E> {
    public boolean isInternal(Position<E> p) {return numChildren(p)>0;}
    public boolean isExternal(Position<E> p) {return numChildren(p)<0;}
    public boolean isRoot(Position<E> p) {return p==root();}
    public boolean isEmpty(){return size()==0;}

    // ∗ Returns the number of levels separating Position p from the root. ∗/
    public int depth(Position<E> p) {
        if(isRoot(p)) return 0;
        return depth(parent(p)) + 1;
    }

    private int heightBad(){
        int h=0;
        for(Position<E> p: positions()) h=Math.max(h, depth(p));
        return h;
    }

    private int height(Position<E> p){
        int h=0;
        for(Position<E> c: children(p)) h=Math.max(h, 1 + height(c));
        return h;
    }
}

Computing Depth and Height

  • Let p be a position within tree T.

Depth

  • The depth of p can be recursively defined:
    • If p is the root, then the depth of p is 0.
    • Otherwise, the depth of p is one plus the depth of the parent of p.

The running time of depth(p) for position p is O(dp +1), where dp denotes the depth of p in the tree, because the algorithm performs a constant-time recursive step for each ancestor of p. Thus, algorithm depth(p) runs in O(n) worst-case time, where n is the total number of positions of T , because a position of T may have depth n − 1 if all nodes form a single branch. Although such a running time is a function of the input size, it is more informative to characterize the running time in terms of the parameter dp, as this parameter may be much smaller than n.

1
2
3
4
5

// ∗ Returns the number of levels separating Position p from the root. ∗/
public int depth(Position<E> p) {
  if(isRoot(p)) return 0;
  return depth(parent(p)) + 1;
}

Height

  • the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

  • heightBad:

    • a method that computes the height of a tree based on this definition.
    • not very efficient, declare it as a private method of the AbstractTree class (so that it cannot be used by others).
    • positions() iteration runs in O(n) time, where n is the number of positions of T.
    • algorithm heightBad runs in O(n^2) worst-case time.
1
2
3
4
5

private int heightBad(){
    int h=0;
    for(Position<E> p: positions()) h=Math.max(h, depth(p));
    return h;
}
  • height:
    • O(n) worst-case time,
    • The algorithm is recursive, and it progresses in a top-down fashion.
    • If the method is initially called on the root of T , it will eventually be called once for each position of T. This is because the root eventually invokes the recursion on each of its children, which in turn invokes the recursion on each of their children, and so on.
1
2
3
4
5

private int height(Position<E> p) {
    int h=0;
    for(Position<E> p: children(p)) h=Math.max(h, 1 + height(c));
    return h;
}

Binary Tree interface

  • A binary tree is an ordered tree with the following properties:
    • a tree data structure in which each node has at most two children
    • referred to as the left child and right child
    • A left child precedes a right child in the order of children of a node.

  • The subtree rooted at a left or right child of an internal node v is called a left subtree or right subtree, respectively, of v.

  • Full Tree proper:
    • every node has either 0 or 2 children
    • A binary tree that is not proper is improper.
  • Perfect Binary Tree:
    • all nodes have two children
    • and all leave have the same depth
  • Complete Tree:
    • every level except possibly the last is full
    • and all nodes in the last level are as far left as possible

以程式碼實作一棵樹，常用的手法為：先以class TreeNode(或是struct)定義出每顆node能夠指向多少subtree、攜帶哪些資料形態，再以另一個class Tree表示整棵樹，並以root作為樹的存取點：

1
2
3
4
5
6
7
8
9
10

public class BinaryTree {

    // 根节点
    public static TreeNode root;

    public BinaryTree() {
        this.root = null;
    }
}

Binary Tree Abstract Data Type

  1. Defining a BinaryTree Interface
    1. This interface extends the Tree interface to add the three new behaviors.
    2. a binary tree is expected to support all the functionality that was defined for general trees (e.g., root, isExternal, parent), and the new behaviors left, right, and sibling.
  2. Defining an AbstractBinaryTree Base Class
    1. use abstract base classes to promote greater reusability within our code. The AbstractBinaryTree class inherits from the AbstractTree class
    2. It provides additional concrete methods that can be derived from the newly declared left and right methods (which remain abstract).

AbstractBinaryTree class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class AbstractBinaryTree<E> extends AbstractTree<E> implements BinaryTree<E> {

    public Position<E> sibling(Position<E> p){
        Position<E> parent = parent(p);
        if(parent == null) return null;
        if(p==left(parent)) return right(p);
        else return left(p);
    }

    public int numChildren(Position<E> p){
        int count=0;
        if(left(p)!=null) count++;
        if(right(p)!=null) count++;
        return count;
    }

    public Iterable<Position<E>> children(Position<E> p){
        Iterable<Position<E>> snapshot = new ArrayList<>(2);
        if(left(p)!=null) snapshot.add(left(p));
        if(right(p)!=null) snapshot.add(right(p));
        return snapshot;
    }

}
Tree in java2

Binary Tree: A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

Summary: Tree is a hierarchical data structure. Main uses of trees include maintaining hierarchical data, providing moderate access and insert/delete operations. Binary trees are special cases of tree where every node has at most two children.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/* Class containing left and right child of current node and key value*/

class Node {
	int key;
	Node left, right;

	public Node(int item) {
		key = item;
		left = right = null;
	}
}


class BinaryTree {
	// Root of Binary Tree
	Node root;

	// Constructors
	BinaryTree(int key) {
		root = new Node(key);
	}

	BinaryTree() {
		root = null;
	}


  // create a simple tree with 4 nodes
	public static void main(String[] args) {

		BinaryTree tree = new BinaryTree();

		/*create root*/
		tree.root = new Node(1);

		/* following is the tree after above statement
			1
			/ \
		null null	 */

		tree.root.left = new Node(2);
		tree.root.right = new Node(3);

		/* 2 and 3 become left and right children of 1
			1
			/ \
			2	 3
		/ \ / \
		null null null null */


		tree.root.left.left = new Node(4);
		/* 4 becomes left child of 2
					1
				/	 \
			2		 3
			/ \	 / \
			4 null null null
		/ \
		null null
		*/
	}
}
Tree in python1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

myTree = ['a',
         ['b', ['d',[],[]], ['e',[],[]] ],
         ['c', ['f',[],[]], []] ]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])


# The BinaryTree function simply constructs a list with a root node and two empty sublists for the children.
def BinaryTree(r):
    return [r, [], []]


# To add a left subtree to the root of a tree, insert a new list into the second position of the root list.
# If the list already has something in the second position, we need to keep track of it and push it down the tree as the left child of the list we are adding.
def insertLeft(root,newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert( 1, [ newBranch, t, [] ] )
    else:
        root.insert( 1, [ newBranch, [], [] ] )
    return root
# Notice that to insert a left child, we first obtain the (possibly empty) list that corresponds to the current left child. We then add the new left child, installing the old left child as the left child of the new one. This allows us to splice a new node into the tree at any position.


def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])
    return root


def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]


r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))

from test import testEqual

def buildTree():
    r = BinaryTree(3)
    insertRight(r,'c')
    insertLeft(r,'c')
    one_left = getLeftChild(r)
    insertRight(one_left,'d')
    one_right = getRightChild(r)
    insertRight(one_right,'f')
    return r

ttree = buildTree()
testEqual(getRootVal(getRightChild(ttree)),'c')
testEqual(getRootVal(getRightChild(getLeftChild(ttree))),'d')
testEqual(getRootVal(getRightChild(getRightChild(ttree))),'f')
Tree in python 2 - Using nodes and references
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class BinaryTree:
  def __init__(self,rootObj):
    self.key = rootObj
    self.leftChild = None
    self.rightChild = None

  def insertLeft(self,newNode):
    if self.leftChild == None:
      self.leftChild = BinaryTree(newNode)
    else:
      # a node with an existing left child. In the second case, we insert a node and push the existing child down one level in the tree.
      t = BinaryTree(newNode)
      t.leftChild = self.leftChild
      self.leftChild = t

  def insertRight(self,newNode):
    if self.rightChild == None:
      self.rightChild = BinaryTree(newNode)
    else:
      t = BinaryTree(newNode)
      t.rightChild = self.rightChild
      self.rightChild = t

  def getRightChild(self):
    return self.rightChild

  def getLeftChild(self):
    return self.leftChild

  def setRootVal(self,obj):
    self.key = obj

  def getRootVal(self):
    return self.key


r = BinaryTree('a')
print(r.getRootVal())
print(r.getLeftChild())
r.insertLeft('b')
print(r.getLeftChild())
print(r.getLeftChild().getRootVal())
r.insertRight('c')
print(r.getRightChild())
print(r.getRightChild().getRootVal())
r.getRightChild().setRootVal('hello')
print(r.getRightChild().getRootVal())
Relating Internal Nodes to External Nodes in a Proper Binary Tree

In a nonempty proper binary tree T

  • with nE external nodes and nI internal nodes, we have nE = nI + 1.

the above relationship does not hold, in general, for improper binary trees and nonbinary trees, although there are other interesting relationships that do hold.

Implementing Trees

Linked Binary Tree Structure class (Linked Structure for Binary Trees)

  • A natural way to realize a binary tree T is to use a linked structure, with a node that maintains references to the element stored at a position p and to the nodes associated with the children and parent of p.
  • If p is the root of T, then the parent field of p is null.
  • if p does not have a left child (respectively, right child), the associated field is null.
  • The tree itself
    • maintains an instance variable storing a reference to the root node (if any),
    • and a variable size, that represents the overall number of nodes of T.

Operations for Updating a Linked Binary Tree

  • addRoot(e):
  • addLeft(p, e):
  • addRight(p, e):
  • set(p, e):
  • attach(p, T1, T2):

  • remove(p):

  • size, isEmpty: O(1)
  • root, parent, left, right, sibling, children, numChildren: O(1)
  • isInternal, isExternal, isRoot: O(1)
  • addRoot, addLeft, addRight, set, attach, remove: O(1)
  • depth( p): O(dp +1)
  • height: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

package tree;
import list.*;

public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {

    //---------------- nested Node class ----------------
    protected static class Node<E> implements Position<E>{
        private E element;
        private Node<E> parent;
        private Node<E> left;
        private Node<E> right;

        public Node(E e, Node<E> above, Node<E> leftChild, Node<E> rightChild) {
            element = e;
            parent = above;
            left = leftChild;
            right = rightChild;
        }

        // accessor methods
        public E getElement() { return element; }
        public Node<E> getParent() { return parent; }
        public Node<E> getLeft() { return left; }
        public Node<E> getRight() { return right; }
        // update methods
        public void setElement(E e) { element = e; }
        public void setParent(Node<E> parentNode) { parent = parentNode; } public void setLeft(Node<E> leftChild) { left = leftChild; }
        public void setRight(Node<E> rightChild) { right = rightChild; }
    }


    // /∗∗ Factory function to create a new node storing element e. ∗/
    protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right) {
        return new Node<E>(e, parent, left, right);
    }

    // LinkedBinaryTree instance variables
    protected Node<E> root = null;
    private int size = 0;

    // constructor
    public LinkedBinaryTree() { }

    // nonpublic utility
    // /∗∗ Validates the position and returns it as a node. ∗/
    protected Node<E> validate(Position<E> p) throws IllegalArgumentException{
        if( ! (p instanceof Node) ) throw new IllegalArgumentException("Not valid position type");
        Node<E> node = (Node<E>) p;
        if(node.getParent()==node) throw new IllegalArgumentException("p is no longer in the tree");
        return node;
    }

    // accessor methods (not already implemented in AbstractBinaryTree)
    public int size() {return size;}
    public Position<E> root() {return root;}
    public Position<E> parent(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getParent();
    }
    public Position<E> left(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getLeft();
    }
    public Position<E> right(Position<E> p) throws IllegalArgumentException {
        Node<E> node = validate(p);
        return node.getRight();
    }

    public Position<E> addRoot(E e) throws IllegalStateException{
        if (!isEmpty( )) throw new IllegalStateException("Tree is not empty");
        root = createNode(e, null, null, null);
        size = 1;
        return root;
    }

    public Position<E> addLeft(Position<E> p, E e) throws IllegalStateException{
        Node<E> parent = validate(p);
        if(parent.getLeft()!=null) throw new IllegalArgumentException("p already has a left child");
        Node<E> child = createNode(e, parent, null, null);
        parent.setLeft(child);
        size++;
        return child;
    }

    public Position<E> addRight(Position<E> p, E e) throws IllegalStateException{
        Node<E> parent = validate(p);
        if(parent.getRight()!=null) throw new IllegalArgumentException("p already has a right child");
        Node<E> child = createNode(e, parent, null, null);
        parent.setRight(child);
        size++;
        return child;
    }

    public E set(Position<E> p, E e) throws IllegalStateException{
        Node<E> node = validate(p);
        E temp = node.getElement();
        node.setElement(e);
        return temp;
    }

    // /∗∗ Attaches trees t1 and t2 as left and right subtrees of external p. ∗/
    public void attach(Position<E> p, LinkedBinaryTree<E> t1, LinkedBinaryTree<E> t2) throws IllegalArgumentException{
        Node<E> node = validate(p);
        if (isInternal(p)) throw new IllegalArgumentException("p must be a leaf");
        size+= t1.size() + t2.size();
        if(!t1.isEmpty()){
            t1.root.setParent(node);
            node.setLeft(t1.root);
            t1.root = null;
            t1.size=0;
        }
        if(!t2.isEmpty()){
            t2.root.setParent(node);
            node.setRight(t2.root);
            t2.root = null;
            t2.size=0;
        }
    }

    // Removes the node at Position p and replaces it with its child, if any. ∗
    public E remove(Position<E> p) throws IllegalArgumentException{
        Node<E> node = validate(p);
        if (numChildren(p) == 2) throw new IllegalArgumentException("p has two children");
        Node<E> child = node.getLeft()!=null? node.getLeft():node.getRight();
        if(child!=null) child.setParent(node.getParent());
        if(node==root) root=child;
        else {
            Node<E> parent = node.getParent();
            if(node == parent.getLeft()) parent.setLeft(child);
            else parent.setRight(child);
        }
        size--;
        E temp = node.getElement();
        // help garbage collection
        node.setElement(null);
        node.setLeft(null);
        node.setRight(null);
        // our convention for defunct node
        node.setParent(node);
        return temp;
    }
}

Linked Binary Tree Structure class (Array-Based Structure for Binary Trees)

  • numbering the positions of T .
    • For every position p of T , let f ( p) be the integer defined as follows.
    • If p is the root of T,then f(p)=0.
    • If p is the left child of position q, then f(p) = 2*f(q)+1.
    • If p is the right child of position q, then f(p) = 2*f(q)+2.

The numbering function f is known as a level numbering of the positions in a binary tree T , for it numbers the positions on each level of T in increasing order from left to right.

Screen Shot 2022-03-21 at 03.12.08

an array-based representation of a binary tree

Screen Shot 2022-03-21 at 03.13.09

One advantage of an array-based representation of a binary tree is that a position p can be represented by the single integer f(p)

  • position-based methods such as root, parent, left, and right can be implemented using simple arithmetic operations on the number f(p).
  • Based on level numbering, the left child of p has index 2f(p)+1, the right child of p has index 2f(p)+2, and the parent of p has index ⌊( f ( p) − 1)/2⌋.

Linked Structure for General Trees

  • For a general tree, there is no a priori limit on the number of children that a node may have.
  • A natural way to realize a general tree T as a linked structure is to have each node store a single container of references to its children.
    • For example, a children field of a node can be an array or list of references to the children of the node (if any).

Screen Shot 2022-03-21 at 03.46.09

Types of BT

Screen Shot 2021-09-15 at 8.28.09 PM

Full Binary Tree 要么有要么没

every node has either 0 or 2 children

  • number of leaf nodes is the number of internal nodes plus 1:
    • Number of leaf nodes = Number of internal nodes + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

               18
           /       \
         15         30
        /  \        /  \
      40    50    100   40

             18
           /    \
         15     20
        /  \
      40    50
    /   \
   30   50

               18
            /     \
          40       30
                   /  \
                 100   40

Perfect Binary Tree

all nodes have two children and all leave have the same depth

  • 所有internal node都有兩個subtree(child pointer)

  • 所有leaf node具有相同的level(或相同的height)。

  • 由以上性質能夠推論出：
    • 若leaf node之level為n，整棵樹共有 2^n − 1個node。
  • 並且，每個node與其child有以下關係：
    • 第i個node的left child之index為 2i；
    • 第i個node的right child之index為 2i+1；
    • 除了root之parent為NULL之外，第i個node的parent之index為 ⌊i/2⌋ 。
1
2
3
4
5
6
7
8
9
10

               18
           /       \
         15         30
        /  \        /  \
      40    50    100   40


               18
           /       \
         15         30

Complete Binary Tree

every level except possibly the last is full and all nodes in the last level are as far left as possible

  • node按照Full Binary Tree的次序排列(由上至下，由左至右)
    • 樹共有10個node，
    • 且這十個node正好填滿Full Binary Tree的前十個位置，
    • 則此樹為Complete Binary Tree。
  • if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible
1
2
3
4
5
6
7
8
9
10
11
12
13
14

               18
           /       \
         15         30
        /  \        /  \
      40    50    100   40


               18
           /       \
         15         30
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9

f4

Complete Binary Tree。

f5

不是一棵Complete Binary Tree。

property of a complete tree

heapOrder

  • can represent it using a single list.
    • no need to use nodes and references or even lists of lists.
  • Because the tree is complete,
  • the left child of a parent (at position 𝑝 ) is the node that is found in position 2𝑝 in the list.
  • Similarly, the right child of the parent is at position 2𝑝+1 in the list.
  • To find the parent of any node in the tree, Given that a node is at position 𝑛 in the list, the parent is at position 𝑛/2

The list representation of the tree, along with the full structure property, allows us to efficiently traverse a complete binary tree using only a few simple mathematical operations.

Balanced Binary Tree

  • A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes.
  • For Example, the AVL tree maintains O(Log n) height by making sure that the difference between the heights of the left and right subtrees is almost 1.
  • Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths is the same and there are no adjacent red nodes.
  • performance-wise good: woest: O(log n) time for search, insert and delete.

degenerate / pathological tree

  • A Tree where every internal node has one child. Such trees are performance-wise same as linked list.
1
2
3
4
5
6
7

      10
      /
    20
     \
     30
      \
      40

Tree Traversal Algorithms: visiting the positions of a tree

  • A traversal of a tree T is a systematic way of accessing, or “visiting,” all the positions of T .
  • The specific action associated with the “visit” of a position p depends on the application of this traversal, and could involve anything from incrementing a counter to performing some complex computation for p.

Preorder and Postorder Traversals of General Trees

Running-Time Analysis

  • Both preorder and postorder traversal algorithms are efficient ways to access all the positions of a tree.
  • At each position p, the nonrecursive part of the traversal algorithm requires time O(cp + 1), where cp is the number of children of p, under the assumption that the “visit” itself takes O(1) time.
  • the overall running time for the traversal of tree T is O(n), where n is the number of positions in the tree.
  • This running time is asymptotically optimal since the traversal must visit all n positions of the tree.

preorder traversal N-L-R General Visit() -> each child preorder(c)

In a preorder traversal of a tree T

  • the root of T is visited first and then the subtrees rooted at its children are traversed recursively.
  • If the tree is ordered, then the subtrees are traversed according to the order of the children.
Algorithm

preorder(p):

  1. perform the “visit” action for position p { this happens before any recursion }
  2. for each child c in children(p) do
    1. preorder(c) { recursively traverse the subtree rooted at c }

Screen Shot 2022-03-21 at 03.55.20

Screen Shot 2020-07-23 at 01.29.46

10 -> 7 -> 6 -> 1 -> 8 -> 9 -> 11 -> 20 -> 14 -> 22

1
2
3
4
5
6
7

             10
           /     \
          7       11
        /  \        \
       6    8        20
      /      \      /  \
     1        9    14  22

Screen Shot 2020-07-24 at 14.39.24

preorder in java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class TreeTraversals {

    public void preOrder(Node root){
        if(root == null){return;}
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public void preOrderItr(Node root){
        Deque<Node> stack = new LinkedList<Node>();
        stack.addFirst(root);
        while(!stack.isEmpty()){
            root = stack.pollFirst();
            System.out.print(root.data + " ");

            if(root.right != null){stack.addFirst(root.right);}
            if(root.left!= null){stack.addFirst(root.left);}
        }
    }
}

preorder in python

1
2
3
4
5
6
7
8
9
10
11
12

def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

def preorder(self):
    print(self.key)
    if self.leftChild:
        self.leftChild.preorder()
    if self.rightChild:
        self.rightChild.preorder()

The answer is that implementing preorder as an external function is probably better in this case.

  • The reason is that you very rarely want to just traverse the tree.
  • In most cases you are going to want to accomplish something else while using one of the basic traversal patterns.

postorder traversal L-R-N General Each child preorder(c) -> Visit()

postorder traversal.

  • can be viewed as the opposite of the preorder traversal, because it recursively traverses the subtrees rooted at the children of the root first, and then visits the root (hence, the name “postorder”).
Algorithm

postorder(p):

  1. for each child c in children(p) do
    1. postorder(c) { recursively traverse the subtree rooted at c }
  2. perform the “visit” action for position p { this happens after any recursion }

Screen Shot 2022-03-21 at 03.58.42

1 -> 6 -> 9 -> 8 -> 7 -> 14 -> 22 -> 20 -> 11 -> 10

1
2
3
4
5
6
7

             10
           /     \
          7       11
        /  \        \
       6    8        20
      /      \      /  \
     1        9    14  22

postorder in java

Screen Shot 2020-07-24 at 13.57.34

Screen Shot 2020-07-24 at 14.00.03

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

public cass TreeTraversals {

    public void postOrder(Node root){
        if(root == null){return;}
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }

    // 1.
    public void iterPostOrder(Node root){
        if (root==null) {return;}
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(root);
        while (!s1.isEmpty()){
            root=s1.pop();
            s2.push(root);
            if (root.left != null) {
                s1.push(root.left);
            }
            if (root.right != null) {
                s1.push(root.right);
            }
        }
        while (!s2.isEmpty()){
            root=s2.pop();
            System.out.println(root.data)
        }
    }

    // 2.
    public void postOrderItr(Node root){
        Deque<Node> stack1 = new LinkedList<Node>();
        Deque<Node> stack2 = new LinkedList<Node>();
        stack1.addFirst(root);
        while(!stack1.isEmpty()){
            root = stack1.pollFirst();
            if(root.left != null){
                stack1.addFirst(root.left);
            }
            if(root.right != null){
                stack1.addFirst(root.right);
            }
            stack2.addFirst(root);
        }
        while(!stack2.isEmpty()){
            System.out.print(stack2.pollFirst().data + " ");
        }
    }

    public void postOrderItrOneStack(Node root){
        Node current = root;
        Deque<Node> stack = new LinkedList<>();
        while(current != null || !stack.isEmpty()){
            if(current != null){
                stack.addFirst(current);
                current = current.left;
            }else{
                Node temp = stack.peek().right;
                if (temp == null) {
                    temp = stack.poll();
                    System.out.print(temp.data + " ");
                    while (!stack.isEmpty() && temp == stack.peek().right) {
                        temp = stack.poll();
                        System.out.print(temp.data + " ");
                    }
                } else {
                    current = temp;
                }
            }
        }
    }
}

postorder in python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def postorder(tree):
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

def postordereval(tree):
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
    res1 = None
    res2 = None
    if tree:
        res1 = postordereval(tree.getLeftChild())
        res2 = postordereval(tree.getRightChild())
        if res1 and res2:
            return opers[tree.getRootVal()](res1,res2)
        else:
            return tree.getRootVal()

BFS and DFS

  1. 为什么 BFS 可以找到最短距离，DFS 不行吗？
    1. BFS 的逻辑，depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。
    2. DFS 也是可以的，但是时间复杂度相对高很多。DFS 实际上是靠递归的堆栈记录走过的路径，找最短路径得把二叉树中所有树杈都探索完, 才能对比出最短的路径有多长
    3. BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。
    4. 形象点说，DFS 是线，BFS 是面；DFS 是单打独斗，BFS 是集体行动
  2. 既然 BFS 那么好，为啥 DFS 还要存在？
    1. BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。
    2. 假设二叉树是满二叉树，节点数为 N
      1. 对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是 O(logN)。
      2. BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 N/2，用 Big O 表示的话也就是 O(N)。
    3. 由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。
BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度可能比 DFS 大很多

BFS - Breadth-First Tree Traversal General Queue()

preorder and postorder traversals are common ways of visiting the positions of a tree, another approach is to traverse a tree so that we visit all the positions at depth d before we visit the positions at depth d + 1. Such an algorithm is known as a breadth-first traversal.

breadth-first traversal

  • visit all the positions at depth d before we visit the positions at depth d + 1.

BFS 出现的常见场景

  • 问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离
  • BFS 算法问题其实都是在干这个事儿，
    • 比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？
    • 比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？
    • 比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？
    • playing games.
      • A game tree represents the possible choices of moves made by a player (or computer) during a game,
      • with the root of the tree being the initial configuration for the game.
      • For example, game tree for Tic-Tac-Toe.
  • 本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。

A breadth-first traversal of such a game tree is often performed because a computer may be unable to explore a complete game tree in a limited amount of time. So the computer will consider all moves, then responses to those moves, going as deep as computational time allows.

BFS Pseudocode

  • The process is not recursive, since we are not traversing entire subtrees at once.
  • We use a queue to produce a FIFO (i.e., first-in first-out) semantics for the order in which we visit nodes.
  • The overall running time is O(n), due to the n calls to enqueue and n calls to dequeue.
Algorithm

breadthfirst():

  1. Initialize queue Q to contain root()
  2. while Q not empty do
    1. p = Q.dequeue() { p is the oldest entry in the queue }
    2. perform the visit action for position p
    3. for each child c in children(p) do
      1. Q.enqueue(c) { add p’s children to the end of the queue for later visits }

BFS in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// /∗∗ Returns an iterable collection of positions of the tree in breadth-first order. ∗/
public Iterable<Position<E>> breadthfirst() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty()) {
        Queue<Position<E>> fringe = new LinkedQueue<>();
        fringe.enqueue(root());
        while(!fringe.isEmpty()){
            Position<E> p = fringe.dequeue();
            snapshot.add(p);
            for(Position<E> c: children(p)){
                fringe.enqueue(c);
            }
        }
    }
    return snapshot;
}


// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    // 将起点加入队列
    q.offer(start);
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target) return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

inorder traversal L-N-R Binary tree

traversal algorithm specifically for a binary tree.

  • visit a position between the recursive traversals of its left and right subtrees.
  • The inorder traversal of a binary tree T can be informally viewed as visiting the nodes of T “from left to right.”
  • Indeed, for every position p, the inorder traversal visits p after all the positions in the left subtree of p and before all the positions in the right subtree of p.

Screen Shot 2022-03-28 at 22.15.10

Screen Shot 2020-07-23 at 01.33.45

1 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 14 -> 20 > 22

1
2
3
4
5
6
7

             10
           /     \
          7       11
        /  \        \
       6    8        20
      /      \      /  \
     1        9    14  22

Pseudocode

Algorithm

inorder(p):

  1. if p has a left child lc then
    1. inorder(lc) { recursively traverse the left subtree of p }
  2. perform the “visit” action for position p
  3. if p has a right child rc then
    1. inorder(rc) { recursively traverse the right subtree of p }

inorder in java

O(n)

Screen Shot 2020-07-25 at 00.40.01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

public class TreeTraversals {

    public void inOrder(Node root){
        if(root == null){return;}
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }

    public void inorderItr(Node root){
        if (root==null) return;
        Stack<Node> s = new Stack<Node>();
        while (true) {
            if (root != null) {
                s.push(root);
                root=root.left;
            }
            else {
                if (s.isEmpty()) {
                    break;
                }
                root=s.pop();
                System.out.print(root);
                root = root.right;
            }
        }
    }



    public void inorderItr(Node root){
        Stack stack = new Stack();
        stack.push(root);

        if (root.left == null) {
            return stack.pop(root);
        }
        if (root.left != null) {
            return inorderItr(root.left);
            stack.pop(root)
            stack.pop(root.right)
        }
    }

    // public void inorderItr(Node root){
    //     Deque<Node> stack = new LinkedList<Node>();
    //     Node node = root;
    //     while(true){
    //         if(node != null){
    //             stack.addFirst(node);
    //             node = node.left;
    //         }
    //         else{
    //             if(stack.isEmpty()){
    //                 break;
    //             }
    //             node = stack.pollFirst();
    //             System.out.println(node.data);
    //             node = node.right;
    //         }
    //     }
    // }
}

inorder in python

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def inorder(tree):
  if tree != None:
      inorder(tree.getLeftChild())
      print(tree.getRootVal())
      inorder(tree.getRightChild())

def printexp(tree):
  sVal = ""
  if tree:
      sVal = '(' + printexp(tree.getLeftChild())
      sVal = sVal + str(tree.getRootVal())
      sVal = sVal + printexp(tree.getRightChild())+')'
  return sVal

application

The inorder traversal algorithm has several important applications.

  • When using a binary tree to represent an arithmetic expression, the inorder traversal visits positions in a consistent order with the standard representation of the expression, as in 3 + 1 × 3/9 − 5 + 2 . . . (albeit without parentheses).

BST - Binary Search Trees 左小右大

  • a type of binary tree
  • maintains the property that：
    • the value in each node must be
    • greater than or equal to any value stored in the left sub-tree,
    • and less than or equal to any value stored in the right sub-tree

bst property

  • store an ordered sequence of elements in a binary tree, defining structure binary search tree.
  • Let S be a set whose unique elements have an order relation.
    • For example, S could be a set of integers.
    • A binary search tree for S is a proper binary tree T such that, for each internal position p of T :
      • subtree_v(left) < value(center) < subtree_v(right)
      • Position p stores an element of S, denoted as e(p).
      • Elements stored in the left subtree of p (if any) are less than e(p).
      • Elements stored in the right subtree of p (if any) are greater than e(p).
  • A binary search tree relies on the property that
    • keys that are less than the parent are found in the left subtree,
    • keys that are greater than the parent are found in the right subtree.
  • We call this the bst property.

the running time of searching in a binary search tree T is proportional to the height of T .

  • the height of a binary tree with n nodes: log(n+1)−1 ~ n−1

Time Complexity:

  • Access: O(log(n))
  • Search: O(log(n))
  • Insert: O(log(n))
  • Remove: O(log(n))

As we implement the Map interface as described above, the bst property will guide our implementation.

simpleBST

Implementing Tree Traversals in Java

any of the tree traversal algorithms can be used to produce these iterations as concrete implementations within the AbstractTree or AbstractBinaryTree base classes.

Preorder Traversals
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public Iterable<Position<E>> positions() { return preorder(); }

// ∗∗ Returns an iterable collection of positions of the tree, reported in preorder. ∗/
public Iterable<Position<E>> preorder() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty()) preorderSubtree(root(), snapshot); // fill the snapshot recursively
    return snapshot;
}

// ∗∗ Adds positions of the subtree rooted at Position p to the given snapshot. ∗/
private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
    snapshot.add(p); // for preorder, we add position p before exploring subtrees
    for (Position<E> c : children(p)) preorderSubtree(c, snapshot);
}
Postorder Traversal
  • implement a postorder traversal using a similar design as we used for a preorder traversal.
  • The only difference is that a “visited” position is not added to a postorder snapshot until after all of its subtrees have been traversed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

// ∗∗ Returns an iterable collection of positions of the tree, reported in preorder. ∗/
public Iterable<Position<E>> postorder() {
    List<Position<E>> snapshot = new ArrayList<>();
    if (!isEmpty()) postorderSubtree(root(), snapshot); // fill the snapshot recursively
    return snapshot;
}

// ∗∗ Adds positions of the subtree rooted at Position p to the given snapshot. ∗/
private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
    snapshot.add(p); // for preorder, we add position p before exploring subtrees
    for (Position<E> c : children(p)) postorderSubtree(c, snapshot);
}
Inorder Traversal
1
2
3
4
5
6
7
8
9
10
11
12
13

    // ∗∗ Returns an iterable collection of positions of the tree, reported in inorder. ∗/
    public Iterable<Position<E>> inorder() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty()) inorderSubtree(root(), snapshot); // fill the snapshot recursively
        return snapshot;
    }

    // ∗∗ Adds positions of the subtree rooted at Position p to the given snapshot. ∗/
    private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) {
        if (left(p) != null) inorderSubtree(left(p), snapshot);
        snapshot.add(p);
        if (right(p) != null) inorderSubtree(right(p), snapshot);
    }
Implementing Tree Traversals in Python

To implement the binary search tree, we will use the nodes and references approach similar to the one we used to implement the linked list, and the expression tree.

However, because we must be able create and work with a binary search tree that is empty, our implementation will use two classes.

  • The first class we will call BinarySearchTree,
  • and the second class we will call TreeNode.

the interface provided by the map ADT.

  • Map()
    • Create a new, empty map.
  • put(key,val)
    • Add a new key-value pair to the map.
    • If the key is already in the map then replace the old value with the new value.
  • get(key)
    • Given a key, return the value stored in the map or None otherwise.
  • del
    • Delete the key-value pair from the map using a statement of the form del map[key].
  • len()
    • Return the number of key-value pairs stored in the map.
  • in
    • Return True for a statement of the form key in map, if the given key is in the map.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def spliceOut(self):
        if self.isLeaf():
            if self.isLeftChild():
                self.parent.leftChild = None
            else:
                self.parent.rightChild = None
        elif self.hasAnyChildren():
            if self.hasLeftChild():
                if self.isLeftChild():
                    self.parent.leftChild = self.leftChild
                else:
                    self.parent.rightChild = self.leftChild
                self.leftChild.parent = self.parent
            else:
                if self.isLeftChild():
                    self.parent.leftChild = self.rightChild
                else:
                    self.parent.rightChild = self.rightChild
                self.rightChild.parent = self.parent

    def findSuccessor(self):
        succ = None
        if self.hasRightChild():
            succ = self.rightChild.findMin()
        else:
            if self.parent:
                   if self.isLeftChild():
                       succ = self.parent
                   else:
                       self.parent.rightChild = None
                       succ = self.parent.findSuccessor()
                       self.parent.rightChild = self
        return succ

    def findMin(self):
        current = self
        while current.hasLeftChild():
            current = current.leftChild
        return current

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
       self.put(k,v)

    def get(self,key):
       if self.root:
           res = self._get(key,self.root)
           if res:
                  return res.payload
           else:
                  return None
       else:
           return None

    def _get(self,key,currentNode):
       if not currentNode:
           return None
       elif currentNode.key == key:
           return currentNode
       elif key < currentNode.key:
           return self._get(key,currentNode.leftChild)
       else:
           return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
       return self.get(key)

    def __contains__(self,key):
       if self._get(key,self.root):
           return True
       else:
           return False

    def delete(self,key):
      if self.size > 1:
         nodeToRemove = self._get(key,self.root)
         if nodeToRemove:
             self.remove(nodeToRemove)
             self.size = self.size-1
         else:
             raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
         self.root = None
         self.size = self.size - 1
      else:
         raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
       self.delete(key)

    def remove(self,currentNode):
         if currentNode.isLeaf(): #leaf
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
         elif currentNode.hasBothChildren(): #interior
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload

         else: # this node has one child
           if currentNode.hasLeftChild():
             if currentNode.isLeftChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.leftChild
             elif currentNode.isRightChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.leftChild
             else:
                 currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
           else:
             if currentNode.isLeftChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.rightChild
             elif currentNode.isRightChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.rightChild
             else:
                 currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

BinarySearchTree class

The BinarySearchTree class has a reference to the TreeNode that is the root of the binary search tree.

  • In most cases the external methods defined in the outer class simply check to see if the tree is empty.
  • If there are nodes in the tree, the request is just passed on to a private method defined in the BinarySearchTree class that takes the root as a parameter.
  • In the case where the tree is empty or we want to delete the key at the root of the tree, we must take special action.
1
2
3
4
5
6
7
8
9
10
11

class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self): return self.size

    def __len__(self): return self.size

    def __iter__(self): return self.root.__iter__()

TreeNode class

The TreeNode class provides many helper functions that make the work done in the BinarySearchTree class methods much easier.

  • many of these helper functions help to classify a node according to its own position as a child, (left or right) and the kind of children the node has.
  • The TreeNode class will also explicitly keep track of the parent as an attribute of each node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class TreeNode:
   def __init__(self,key,val,
                left=None,right=None,
                parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self): return self.leftChild

    def hasRightChild(self): return self.rightChild

    def isLeftChild(self): return self.parent and self.parent.leftChild == self

    def isRightChild(self): return self.parent and self.parent.rightChild == self

    def isRoot(self): return not self.parent

    def isLeaf(self): return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self): return self.rightChild or self.leftChild

    def hasBothChildren(self): return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self

put method

put method

  • to build our binary search tree.
  • The put method is a method of the BinarySearchTree class.
  • This method will check to see if the tree already has a root.
    • If there is not a root then put will create a new TreeNode and install it as the root of the tree.
    • If a root node is already in place then put calls the private, recursive, helper function _put to search the tree according to the following algorithm:
      • Starting at the root of the tree,
        • search the binary tree comparing the new key to the key in the current node.
        • If the new key is less than the current node, search the left subtree.
        • If the new key is greater than the current node, search the right subtree.
      • When there is no left (or right) child to search,
        • we have found the position in the tree where the new node should be installed.
      • To add a node to the tree,
        • create a new TreeNode object
        • and insert the object at the point discovered in the previous step.
1
2
3
4
5
6
7
8
9
10
11
12
13

def put(self,key,val):
    if self.root:
      self._put(key,val,self.root)
    else: self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild(): self._put(key,val,currentNode.leftChild)
        else: currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild(): self._put(key,val,currentNode.rightChild)
        else: currentNode.rightChild = TreeNode(key,val,parent=currentNode)

One important problem with our implementation of insert is that duplicate keys are not handled properly.

  • As our tree is implemented a duplicate key will create a new node with the same key value in the right subtree of the node having the original key.
  • The result of this is that the node with the new key will never be found during a search.
  • A better way to handle the insertion of a duplicate key is for the value associated with the new key to replace the old value.
  • We leave fixing this bug as an exercise for you.

__setitem__ method

overload the [] operator for assignment by having the __setitem__ method call (see Listing 4) the put method.

  • This allows us to write Python statements like myZipTree['Plymouth'] = 55446, just like a Python dictionary.
1
2

def __setitem__(self,k,v):
    self.put(k,v)

get method

  • implement the retrieval of a value for a given key.
  • The get method is even easier than the put method because it simply searches the tree recursively until it gets to a non-matching leaf node or finds a matching key.
  • When a matching key is found, the value stored in the payload of the node is returned.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def get(self,key):
    if self.root:
        res = self._get(key, self.root)
        if res: return res.payload
        else: return None
    else: return None

def _get(self, key, currentNode):
    if not currentNode:
        return None
    elif currentNode.key == key:
        return currentNode

    elif key < currentNode.key:
        return self._get(key,currentNode.leftChild)
    else:
        return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
    return self.get(key)

in method

  • implement the in operation by writing a __contains__ method for the BinarySearchTree.
  • The __contains__ method will simply call get and return True if get returns a value, or False if it returns None.
  • The code for __contains__ is shown in Listing 6.
1
2
3

def __contains__(self,key):
    if self._get(key, self.root): return True
    else: return False

del method

  • the most challenging method in the binary search tree
  • The first task is to find the node to delete by searching the tree.
  • If the tree has more than one node, search using the _get method to find the TreeNode that needs to be removed.
  • If the tree only has a single node, that means removing the root of the tree, but we still must check to make sure the key of the root matches the key that is to be deleted.
  • In either case if the key is not found the del operator raises an error.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def delete(self,key):
  # search the tree
  if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError('Error, key not in tree')
  # key is the root
  elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
  # empty tree
  else:
      raise KeyError('Error, key not in tree')

def __delitem__(self,key):
    self.delete(key)

found the node containing the key we want to delete, there are three cases must consider:

  • The node to be deleted has no children
  • The node to be deleted has only one child
  • The node to be deleted has two children

The node to be deleted has no children

1
2
3
4
5
6

# The node to be deleted has no children
if currentNode.isLeaf():
    if currentNode == currentNode.parent.leftChild:
        currentNode.parent.leftChild = None
    else:
        currentNode.parent.rightChild = None

The node to be deleted has only one child

  • If a node has only a single child, then we can simply promote the child to take the place of its parent.
  • there are six cases to consider.
  • discuss the case where the current node has a left child.
    • If the current node is a left child
      • then we only need to update the parent reference of the left child to point to the parent of the current node,
      • and then update the left child reference of the parent to point to the current node’s left child.
    • If the current node is a right child
      • then we only need to update the parent reference of the left child to point to the parent of the current node,
      • and then update the right child reference of the parent to point to the current node’s left child.
    • If the current node has no parent, it must be the root.
      • In this case we will just replace the key, payload, leftChild, and rightChild data by calling the replaceNodeData method on the root.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# this node has one child
else:
  # leftchild -> currentNode
  if currentNode.hasLeftChild():
      # LeftChild -> parent
      if currentNode.isLeftChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.leftChild
      # parent <- RightChild
      elif currentNode.isRightChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.leftChild
      else:
          currentNode.replaceNodeData(currentNode.leftChild.key,
                                      currentNode.leftChild.payload,
                                      currentNode.leftChild.leftChild,
                                      currentNode.leftChild.rightChild)
  # currentNode <- RightChild
  else:
      if currentNode.isLeftChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.rightChild
      elif currentNode.isRightChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.rightChild
      else:
          currentNode.replaceNodeData(currentNode.rightChild.key,
                             currentNode.rightChild.payload,
                             currentNode.rightChild.leftChild,
                             currentNode.rightChild.rightChild)

The node to be deleted has two children

  • The third case is the most difficult case to handle
  • If a node has two children, then it is unlikely that we can simply promote one of them to take the node’s place.
  • however, search the tree for a node that can be used to replace the one scheduled for deletion.
  • find a node that will preserve the binary search tree relationships for both of the existing left and right subtrees.
  • The node that will do this is the node that has the next-largest key in the tree. We call this node the successor, and we will look at a way to find the successor shortly.
  • The successor is guaranteed to have no more than one child, so we know how to remove it using the two cases for deletion that we have already implemented.
  • Once the successor has been removed, we simply put it in the tree in place of the node to be deleted.
  • make use of the helper methods findSuccessor and findMin to find the successor.
  • To remove the successor, we make use of the method spliceOut.
    • it goes directly to the node to splice out and makes the right changes.
    • We could call delete recursively, but then we would waste time re-searching for the key node.

The code to find the successor is a method of the TreeNode class.

  • This code makes use of the same properties of binary search trees that cause an inorder traversal to print out the nodes in the tree from smallest to largest.
  • There are three cases to consider when looking for the successor:
    • If the node has a right child, then the successor is the smallest key in the right subtree.
    • If the node has no right child and is the left child of its parent, then the parent is the successor.
    • If the node is the right child of its parent, and itself has no right child, then the successor to this node is the successor of its parent, excluding this node.

The findMin method is called to find the minimum key in a subtree.

  • the minimum valued key in any binary search tree is the leftmost child of the tree.
  • Therefore the findMin method simply follows the leftChild references in each node of the subtree until it reaches a node that does not have a left child.
1
2
3
4
5
6

#interior
elif currentNode.hasBothChildren():
  succ = currentNode.findSuccessor()
  succ.spliceOut()
  currentNode.key = succ.key
  currentNode.payload = succ.payload

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild(): current = current.leftChild
    return current

def spliceOut(self):
  if self.isLeaf():
    if self.isLeftChild(): self.parent.leftChild = None
    else: self.parent.rightChild = None
  elif self.hasAnyChildren():
    if self.hasLeftChild():
      if self.isLeftChild(): self.parent.leftChild = self.leftChild
      else: self.parent.rightChild = self.leftChild
      self.leftChild.parent = self.parent
    else:
      if self.isLeftChild():
        self.parent.leftChild = self.rightChild
      else:
        self.parent.rightChild = self.rightChild
      self.rightChild.parent = self.parent

__iter__ iterate over all the keys

to simply iterate over all the keys in the tree in order.

  • using the inorder traversal algorithm.
  • the iterator requires a bit more work, since an iterator should return only one node each time the iterator is called.

yield is similar to return in that it returns a value to the caller.

  • However, yield also takes the additional step of freezing the state of the function so that the next time the function is called it continues executing from the exact point it left off earlier. Functions that create objects that can be iterated are called generator functions.

The code for an inorder iterator of a binary tree is shown in the next listing. Look at this code carefully; at first glance you might think that the code is not recursive. However, remember that __iter__ overrides the for x in operation for iteration, so it really is recursive! Because it is recursive over TreeNode instances the __iter__ method is defined in the TreeNode class.

1
2
3
4
5
6
7
8
9

def __iter__(self):
   if self:
      if self.hasLeftChild():
             for elem in self.leftChiLd:
                yield elem
      yield self.key
      if self.hasRightChild():
             for elem in self.rightChild:
                yield elem
Search Tree Analysis 𝑂(log2𝑛) to 𝑂(𝑛)
  • The number of nodes at any particular level is 2𝑑 where 𝑑 is the depth of the level.

  • The total number of nodes in a perfectly balanced binary tree is 2^(ℎ+1)−1, where ℎ represents the height of the tree.

  • A perfectly balanced tree has the same number of nodes in the left subtree as the right subtree.
  • In a balanced binary tree, the worst-case performance of put is 𝑂(log2𝑛), where 𝑛 is the number of nodes in the tree.
    • this is the inverse relationship to the calculation in the previous paragraph.
    • So log2𝑛 gives us the height of the tree, and represents the maximum number of comparisons that put will need to do as it searches for the proper place to insert a new node.
  • Unfortunately it is possible to construct a search tree that has height 𝑛 simply by inserting the keys in sorted order!
    • In this case the performance of the put method is 𝑂(𝑛)
  • the performance of the put method is limited by the height of the tree, you can probably guess that other methods, get, in, and del, are limited as well. Since get searches the tree to find the key, in the worst case the tree is searched all the way to the bottom and no key is found. At first glance del might seem more complicated, since it may need to search for the successor before the deletion operation can complete. But remember that the worst-case scenario to find the successor is also just the height of the tree which means that you would simply double the work. Since doubling is a constant factor it does not change worst case

Applications of Tree Traversals

Table of Contents

preorder 1 N-L-R

Screen Shot 2022-03-29 at 07.32.16

The unindented version (a)
  • given a tree T supporting the preorder() method:
  • for (Position<E> p : T.preorder()) System.out.println(p.getElement( ));
The version (b)
  • indent each element with a number of spaces equal to twice the element’s depth in the tree
  • given a tree T supporting the preorder() method:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

// the work to produce the preorder traversal runs in O(n) time
// the calls to depth incur a hidden cost.
// Making a call to depth from every position of the tree results in O(n^2) worst-case time
for (Position<E> p : T.preorder()) {
  System.out.println(spaces(2∗T.depth(p)) + p.getElement());
}

// A preferred approach to producing an indented table of contents is to redesign a top-down recursion that includes the current depth as an additional parameter.
// implementation runs in worst-case O(n) time
// ∗∗ Prints preorder representation of subtree of T rooted at p having depth d. ∗/
public static <E> void printPreorderIndent(Tree<E> T, Position<E> p, int d) {
  System.out.println(spaces(2∗d) + p.getElement()); // indent based on d
  for (Position<E> c : T.children(p)) printPreorderIndent(T, c, d+1); // child depth is d+1
}

preorder 2 N-L-R

Screen Shot 2022-03-29 at 07.38.37

  • the numbering was embedded within the elements of the tree.

  • using a preorder traversal to display the structure of a tree, with indentation and also explicit numbering that was not present in the tree.

  • more challenging
    • because the numbers used as labels are implicit in the structure of the tree.
    • label depends on the path from the root to the current position.
  • add an additional parameter to the recursive signature.
    • send a list of integers representing the labels leading to a particular position.
    • For example
    • node Domestic, send the list of values {2,1} that comprise its label.
1
2
3
4
5
6
7
8
9
10
11
12
13

// /∗∗ Prints labeled representation of subtree of T rooted at p having depth d. ∗/
public static <E> void printPreorderLabeled(Tree<E> T, Position<E> p, ArrayList<Integer> path) {
  int d = path.size();           // depth equals the length of the path
  System.out.print(spaces(2*d)); // print indentation, then label
  for (int j=0; j < d; j++) System.out.print(path.get(j) + (j == d−1 ? " " : "."));
  System.out.println(p.getElement( ));
  path.add(1);                   // add path entry for first child
  for (Position<E> c : T.children(p)) {
    printPreorderLabeled(T, c, path); // increment last entry of path
    path.set(d, 1 + path.get(d));
  }
  path.remove(d);// restore path to its incoming state
}

Computing Disk Space postorder L-R-N

  • The recursive computation of disk space is emblematic of a postorder traversal, as we cannot effectively compute the total space used by a directory until after we know the space that is used by its children directories.
  • We would like to have a mechanism for children to return information to the parent as part of the traversal process.
1
2
3
4
5
6

// ∗∗ Returns total disk space for subtree of T rooted at p. ∗/
public static int diskSpace(Tree<Integer> T, Position<Integer> p) {
  int subtotal = p.getElement(); // we assume element represents space usage
  for (Position<Integer> c : T.children(p)) subtotal += diskSpace(T, c);
  return subtotal;
}

Parenthetic Representations of a Tree

  • It is not possible to reconstruct a general tree, given only the preorder sequence of elements
  • Some additional context is necessary for the structure of the tree to be well defined.
  • The use of indentation or numbered labels provides such context, with a very human-friendly presentation.
  • However, there are more concise string representations of trees that are computer-friendly.

one such representation

  • The parenthetic string representation P(T) of tree T is recursively defined.
  • If T consists of a single position p, then P(T ) = p.getElement( ).
  • Otherwise, it is defined recursively as, P(T)= p.getElement()+"("+P(T1)+","+ ··· +","+P(Tk)+")"
    • where p is the root of T and
    • T1,T2,…,Tk are the subtrees rooted at the children of p, which are given in order if T is an ordered tree.
    • We are using “+” here to denote string concatenation.

Screen Shot 2022-03-29 at 07.38.37

  • As an example, the parenthetic representation of the tree of Figure 8.2 would appear as follows (line breaks are cosmetic):
    • Electronics R’Us (R&D, Sales (Domestic, International (Canada, S. America, Overseas (Africa, Europe, Asia, Australia))), Purchasing, Manufacturing (TV, CD, Tuner))

Although the parenthetic representation is essentially a preorder traversal

  • cannot easily produce the additional punctuation using the formal implementation of preorder.
  • The opening parenthesis must be produced just before the loop over a position’s children, the separating commas between children, and the closing parenthesis just after the loop completes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

    // /∗∗ Prints parenthesized representation of subtree of T rooted at p. ∗/
    public static <E> void parenthesize(Tree<E> T, Position<E> p) {
        System.out.print(p.getElement());
        if (T.isInternal(p)) {
            boolean firstTime = true;
            for(Position<E> c : T.children(p)){
                System.out.print( (firstTime ? " (" : ", ") ); // determine proper punctuation
                firstTime = false;
                parenthesize(T, c);
            }
            System.out.print(")");
        }
    }

Using Inorder Traversal for Tree Drawing

An inorder traversal can be applied to compute a graphical layout of a binary tree

  • assume that x-coordinates increase left to right and y-coordinates increase top to bottom,
  • so that the origin is in the upper left corner of the drawing.

Screen Shot 2022-03-30 at 22.28.04

The geometry is determined by an algorithm that

  • assigns x- and y-coordinates to each position p of a binary tree T using the following two rules:
  • x(p) is the number of positions visited before p in an inorder traversal of T.
  • y(p) is the depth of p inT.
1
2
3
4
5
6
7

public static <E> int layout(BinaryTree<E> T, Position<E> p, int d, int x) {
  if (T.left(p) != null) x = layout(T, T.left(p), d+1, x);
  p.getElement().setX(x++);
  p.getElement().setY(d);
  if (T.left(p) != null) x = layout(T, T.left(p), d+1, x);
  return x;
}

Euler Tours

  • not every application strictly fits the mold of a preorder, postorder, or inorder traversal.
  • We can unify the tree-traversal algorithms into a single framework known as an Euler tour traversal.
  • The Euler tour traversal of a tree T can be informally defined as a “walk” around T
    • where we start by going from the root toward its leftmost child, viewing the edges of T as being “walls” that we always keep to our left

Screen Shot 2022-03-30 at 22.39.02

The complexity of the walk is O(n), for a tree with n nodes,

  • because it progresses exactly two times along each of the n − 1 edges of the tree
    • once going downward along the edge,
    • and later going upward along the edge.
  • To unify the concept of preorder and postorder traversals, we can view there being two notable “visits” to each position p:
    • A “pre visit” occurs when first reaching the position, that is, when the walk passes immediately left of the node in our visualization.
    • A “postvisit” occurs when the walk later proceed supward from that position, that is, when the walk passes to the right of the node in our visualization.

The process of an Euler tour can be naturally viewed as recursive.

  • In between the “pre visit” and “post visit” of a given position will be a recursive tour of each of its subtrees.
  • Looking at Figure 8.20 as an example, there is a contiguous portion of the entire tour that is itself an Euler tour of the subtree of the node with element “/”. That tour contains two contiguous subtours, one traversing that position’s left subtree and another traversing the right subtree.
  • In the special case of a binary tree, we can designate the time when the walk passes immediately below a node as an “in visit” event.
    • This will be just after the tour of its left subtree (if any), but before the tour of its right subtree (if any).

pseudocode

  • pseudocode for an Euler tour traversal of a subtree rooted at a position p
Algorithm

eulerTour(T , p):

  • perform the “pre visit” action for position p
  • for each child c in T.children(p) do
    • eulerTour(T , c) { recursively tour the subtree rooted at c }
  • perform the “post visit” action for position p

The Euler tour traversal extends the preorder and postorder traversals, but it can also perform other kinds of traversals. For example, suppose we wish to compute the number of descendants of each position p in an n-node binary tree.

  • We start an Euler tour by initializing a counter to 0, and then increment the counter during the “pre visit” for each position. To determine the number of descendants of a position p, we compute the difference between the values of the counter from when the pre-visit occurs and when the post-visit occurs, and add 1 (for p).
  • This simple rule gives us the number of descendants of p, because each node in the subtree rooted at p is counted between p’s visit on the left and p’s visit on the right.
  • Therefore, we have an O(n)-time method for computing the number of descendants of each node.

For the case of a binary tree, we can customize the algorithm to include an explicit “in visit” action

Algorithm

eulerTourBinary(T , p):

  • perform the “pre visit” action for position p
  • if p has a left child lc then
    • eulerTourBinary(T , lc) { recursively tour the left subtree of p }
  • perform the “in visit” action for position p
  • if p has a right child rc then
    • eulerTourBinary(T , rc) { recursively tour the right subtree of p }
  • perform the “post visit” action for position p

Screen Shot 2022-03-30 at 22.39.02

  • For example
  • binary Euler tour can produce a traditional parenthesized arithmetic expression

    • such as "((((3+1)x3)/((9-5)+2))-((3x(7-4))+6))" for the tree as follows:

    • “Pre visit” action: if the position is internal, print “(”.
    • “In visit” action: print the value or operator stored at the position.
    • “Post visit” action: if the position is internal, print “)”.

Balanced Binary Search Trees

the binary search tree can degrade to 𝑂(𝑛) for operations like get and put when the tree becomes unbalanced.

Balanced Binary Search Trees

  • binary search tree -> the tree remains balanced at all times.
  • This tree is called an AVL tree -> inventors: G.M. Adelson-Velskii and E.M. Landis.

An AVL tree implements the Map abstract data type just like a regular binary search tree,

  • the only difference is in how the tree performs.
  • To implement our AVL tree we need to keep track of a balance factor for each node in the tree.
  • We do this by looking at the heights of the left and right subtrees for each node.
  • balance factor for a node:

    • the difference between the height of the left subtree and the height of the right subtree.

    • 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝐹𝑎𝑐𝑡𝑜𝑟=ℎ𝑒𝑖𝑔ℎ𝑡(𝑙𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒)−ℎ𝑒𝑖𝑔ℎ𝑡(𝑟𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒)

    • 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝐹𝑎𝑐𝑡𝑜𝑟= | ℎ𝑒𝑖𝑔ℎ𝑡(𝑙𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒) − ℎ𝑒𝑖𝑔ℎ𝑡(𝑟𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒) |

    • 𝑏𝑎𝑙𝑎𝑛𝑐𝑒 : | ℎ𝑒𝑖𝑔ℎ𝑡(𝑙𝑒𝑓𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒) − ℎ𝑒𝑖𝑔ℎ𝑡(𝑟𝑖𝑔ℎ𝑡𝑆𝑢𝑏𝑇𝑟𝑒𝑒) | <= 1

    • 𝑏𝑎𝑙𝑎𝑛𝑐𝑒 : 𝑏𝑎𝑙𝑎𝑛𝑐𝑒𝐹𝑎𝑐𝑡𝑜𝑟 <= 1

Screen Shot 2021-09-30 at 1.22.34 PM

Screen Shot 2021-09-30 at 1.24.44 PM

  • a subtree is left-heavy if the balance factor is greater than zero.
  • If the balance factor is less than zero then the subtree is right heavy.
  • If the balance factor is zero then the tree is perfectly in balance.

For purposes of implementing an AVL tree

  • we will define a tree to be in balance if the balance factor is -1, 0, or 1.
  • Once the balance factor of a node in a tree is outside this range we will need to have a procedure to bring the tree back into balance.

AVL Tree Performance

Before we proceed any further let’s look at the result of enforcing this new balance factor requirement.

  • by ensuring tree always has a balance factor of -1, 0, or 1 we can get better Big-O performance of key operations.
  • Let us start by thinking about how this balance condition changes the worst-case tree.
  • There are two possibilities to consider,
  • a left-heavy tree and a right heavy tree.

  • If we consider trees of heights 0, 1, 2, and 3, Figure 2 illustrates the most unbalanced left-heavy tree possible under the new rules.

  • for the number of nodes in a tree of height h: 𝑁ℎ=1+𝑁ℎ−1+𝑁ℎ−2

Root.AVLTree = RChild.AVLTree + LChild.AVLTree

worse case, less node:
  • same height
  • min nodes
  • RChild.AVLTree.Height - LChild.AVLTree.Height <= 1
if not, not balanced:

Screen Shot 2021-09-30 at 9.37.06 PM

derivation

  • This derivation shows us that at any time the height of our AVL tree is equal to a constant(1.44) times the log of the number of nodes in the tree.
  • This is great news for searching our AVL tree because it limits the search to 𝑂(log𝑁).

keeping an AVL tree in balance is going to be a big performance improvement

AVL Tree Implementation

new Node

  • Since all new keys are inserted into the tree as leaf nodes and the balance factor for a new leaf is zero
    • no new requirements for the node that was just inserted.

Node.parent

  • But once the new leaf is added we must update the balance factor of its parent.
    • new leaf affects the parent’s balance factor depends on whether the leaf node is a left child or a right child.
    • If the new node is a right child, the balance factor of the parent - 1
    • If the new node is a left child. then the balance factor of the parent + 1
  • This relation can be applied recursively to the grandparent of the new node, and possibly to every ancestor all the way up to the root of the tree.

updateBalance

  • two base cases for updating balance factors:
    • The recursive call has reached the root of the tree.
    • The balance factor of the parent has been adjusted to zero.
      • once a subtree has a balance factor of zero, then the balance of its ancestor nodes does not change.

Implement the AVL tree as a subclass of BinarySearchTree.

  • verride the _put method and write a new updateBalance helper method.
  • the definition for _put is exactly the same as in simple binary search trees except for the additions of the calls to updateBalance on lines 7 and 13.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def _put(self, key, val, currentNode):
  # -> key will be currentNode.leftchild
  if key < currentNode.key:
    if currentNode.hasLeftChild():
      self._put(key,val, currentNode.leftChild)
    else:
      currentNode.leftChild = TreeNode(key,val,parent=currentNode)
      self.updateBalance(currentNode.leftChild)
  # -> key will be currentNode.rightchild
  else:
    if currentNode.hasRightChild():
      self._put(key,val, currentNode.rightChild)
    else:
      currentNode.rightChild = TreeNode(key,val,parent=currentNode)
      self.updateBalance(currentNode.rightChild)

def updateBalance(self,node):
  # be balenced itself
  if node.balanceFactor > 1 or node.balanceFactor < -1:
    self.rebalance(node)
    return
  # if have parent
  if node.parent != None:
    if node.isLeftChild(): node.parent.balanceFactor += 1
    elif node.isRightChild(): node.parent.balanceFactor -= 1
    # if parent become unbalanced, rebalance it
    if node.parent.balanceFactor != 0:
      self.updateBalance(node.parent)

The new updateBalance method is where most of the work is done.

  • This implements the recursive procedure
    • If the current node is out of balance enough to require rebalancing
      • then the rebalancing is done and no further updating to parents is required.
    • If the current node does not require rebalancing
      • then the balance factor of the parent is adjusted.
    • If the balance factor of the parent is non-zero
      • then the algorithm continues to work its way up the tree toward the root by recursively calling updateBalance on the parent.

rebalance When a rebalancing of the tree is necessary

  • Efficient rebalancing is the key to making the AVL Tree work well without sacrificing performance.
  • In order to bring an AVL Tree back into balance we will perform one or more rotations on the tree.

Screen Shot 2021-09-30 at 9.54.31 PM

Screen Shot 2021-09-30 at 9.55.02 PM

simpleunbalanced

step:

  • Promote the right child (B) to be the root of the subtree.
  • Move the old root (A) to be the left child of the new root.
  • If new root (B) already had a left child then make it the right child of the new left child (A). Note: Since the new root (B) was the right child of A the right child of A is guaranteed to be empty at this point. This allows us to add a new node as the right child without any further consideration.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def rotateLeft(self,rotRoot):
    newRoot = rotRoot.rightChild
    rotRoot.rightChild = newRoot.leftChild
    if newRoot.leftChild != None:
        newRoot.leftChild.parent = rotRoot
    newRoot.parent = rotRoot.parent
    if rotRoot.isRoot():
        self.root = newRoot
    else:
        # make rotroot.parent.child to newroot
        if rotRoot.isLeftChild(): rotRoot.parent.leftChild = newRoot
        else: rotRoot.parent.rightChild = newRoot
    # make rotroot.parent to newroot
    newRoot.leftChild = rotRoot
    rotRoot.parent = newRoot
    rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0)
    newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(rotRoot.balanceFactor, 0)

example:

bfderive

  • 𝑜𝑙𝑑𝐵𝑎𝑙(𝐵)=ℎ𝐴−ℎ𝐷

  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵)=ℎ𝐴−ℎ𝐶

  • 𝑜𝑙𝑑h(D) = 1 + 𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸)

  • 𝑜𝑙𝑑𝐵𝑎𝑙(𝐵)= ℎ𝐴 − (1 + 𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸))

  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵)−𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) = ℎ𝐴−ℎ𝐶 − (ℎ𝐴−(1+𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸)))
  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵)−𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) = ℎ𝐴−ℎ𝐶 − ℎ𝐴 +(1+𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸))
  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵)−𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) = ℎ𝐴−ℎ𝐴 +1 +𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸) −ℎ𝐶
  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵)−𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) = 1 + 𝑚𝑎𝑥(ℎ𝐶,ℎ𝐸) −ℎ𝐶
    • 𝑚𝑎𝑥(𝑎,𝑏)−𝑐 = 𝑚𝑎𝑥(𝑎−𝑐,𝑏−𝑐)

  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵) = 𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) +1 + 𝑚𝑎𝑥(ℎ𝐶−ℎ𝐶,ℎ𝐸−ℎ𝐶)

  • ℎ𝐸−ℎ𝐶 = −𝑜𝑙𝑑𝐵𝑎𝑙(𝐷)

  • 𝑚𝑎𝑥(−𝑎,−𝑏) = −𝑚𝑖𝑛(𝑎,𝑏)

  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵) = 𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) +1 +𝑚𝑎𝑥(0,−𝑜𝑙𝑑𝐵𝑎𝑙(𝐷))
  • 𝑛𝑒𝑤𝐵𝑎𝑙(𝐵) = 𝑜𝑙𝑑𝐵𝑎𝑙(𝐵) +1 −𝑚𝑖𝑛(0,𝑜𝑙𝑑𝐵𝑎𝑙(𝐷))
  • rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(0,newRoot.balanceFactor)

To correct the balance:

  • If a subtree needs a left rotation to bring it into balance,
    • first check the balance factor of the right child.
    • If the right child is left heavy then do a right rotation on right child,
    • followed by the original left rotation.
  • If a subtree needs a right rotation to bring it into balance,
    • first check the balance factor of the left child.
    • If the left child is right heavy then do a left rotation on the left child,
    • followed by the original right rotation.
1
2
3
4
5
6
7
8
9
10
11
12
13

def rebalance(self,node):
  if node.balanceFactor < 0:
         if node.rightChild.balanceFactor > 0:
            self.rotateRight(node.rightChild)
            self.rotateLeft(node)
         else:
            self.rotateLeft(node)
  elif node.balanceFactor > 0:
         if node.leftChild.balanceFactor < 0:
            self.rotateLeft(node.leftChild)
            self.rotateRight(node)
         else:
            self.rotateRight(node)

analyze

By keeping the tree in balance at all times, ensure that the get method will run in order 𝑂(𝑙𝑜𝑔2(𝑛)) time.

cost to our put method

  • Since a new node is inserted as a leaf,
  • updating the balance factors of all the parents will require a maximum of 𝑙𝑜𝑔(𝑛) operations, one for each level of the tree.
  • If a subtree is found to be out of balance a maximum of two rotations are required to bring the tree back into balance.
  • But, each of the rotations works in 𝑂(1) time, so even our put operation remains 𝑂(𝑙𝑜𝑔(𝑛)).

Binary Search Tree code (depth-first)

Binary Search Tree Search in java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class BSTSearch {

    public Node search(Node root, int key) {
        if (root.data == null) { return null;}
        if (root.data == key) { return root;}
        else if (root.data > key) {
            search(root.left, key);
        }
        else {
            search(root.right, key);
        }
    }

    public static void main(String args[]){

        BinaryTree bt = new BinaryTree();
        Node root = null;
        root = bt.addNode(10, root);
        root = bt.addNode(20, root);
        root = bt.addNode(-10, root);
        root = bt.addNode(15, root);
        root = bt.addNode(0, root);
        root = bt.addNode(21, root);
        root = bt.addNode(-1, root);

        BSTSearch bstSearch = new BSTSearch();

        Node result = bstSearch.search(root, 21);
        assert result.data == 21;

        result = bstSearch.search(root, -1);
        assert result.data == 21;

        result = bstSearch.search(root, 11);
        assert result == null;
    }
}

Binary Search Tree Insertion (Iterative method)

worst: O(n)


public class BinaryTree{

    public Node insert(Node root, int data){
        Node node = new Node(data);
        if (root == null) {
            return node;
        }
        Node parent = null;
        Node current = root;
        while (root != null) {
            parent = root;
            if (root.data < data) {
                root = root.right;
            }
            else {
                root = root.left;
            }
        }
        if (parent.data < data) {
            parent.right = data;
        }
        else {
            parent.left = data;
        }
        return parent;

        // if (root.data < key && root.next == null) {
        //     root.left.data == key
        // }
        // if (root.data > key && root.next == null) {
        //     root.left.data == key
        // }
        // if (root.next != null) {
        //     root = root.next;
        //     bstInsert(Node root.next, int key);
        // }
    }
}

Size Of Binary Tree node numebr

Screen Shot 2020-07-24 at 13.30.14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class SizeOfBinaryTree {

    public int size(Node root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }

    public static void main(String args[]){

        BinaryTree bt = new BinaryTree();
        Node head = null;
        head = bt.addNode(10, head);
        head = bt.addNode(15, head);
        head = bt.addNode(5, head);
        head = bt.addNode(7, head);
        head = bt.addNode(19, head);
        head = bt.addNode(20, head);
        head = bt.addNode(-1, head);

        SizeOfBinaryTree sbt = new SizeOfBinaryTree();
        System.out.println(sbt.size(head));
    }
}

check if Balanced

time: O(n) space: O(H)

check Height Of Binary Tree

time & space: O(n)

Screen Shot 2020-07-24 at 13.29.49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class SameTree {

    public int height(Node root){
        if(root == null){
            return 0;
        }
        int leftHeight  = height(root.left);
        int rightHeight = height(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // public int height(Node root){
    //     if(root.left == null && root.right == null) {
    //         return 1;
    //     }
    //     else {
    //         return 0;
    //     }
    //     return 1 + height(root.right) + height(root.left)
    // }
}

Root To Leaf Sum Binary Tree

Screen Shot 2020-07-24 at 13.29.20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Root {

    public boolean RootToLeaf(Node root, int sum, list<Integer result>) {

        if (root == null) {return false;}
        if (root.left == null && root.right == null) {
            if (root.data == sum) {
                result.add(root.data);
                return true;
            }
            else {return false;}
        }

        if (RootToLeaf(Node root.left, int sum-root.data, list<Integer result>)) {
            result.add(root.data);
            return true;
        }
        else {return false;}

        if (RootToLeaf(Node root.right, int sum-root.data, list<Integer result>)) {
            result.add(root.data);
            return true;
        }
        else {return false;}
        return false;
    }
}

Check if Binary Tree is Binary Search Tree

Screen Shot 2020-07-24 at 13.34.44

1
2
3
4
5
6
7
8

public class Root {

    public boolean isBST(Node root, int min, int max) {
        if (root == null) {return true;}
        if (root.data < min || root.data > max) {return false;}
        return isBST(root.left, min, root.data) && isBST(root, root.data, max)
    }
}

Binary Search Tree code (Level Order -> queue)

Screen Shot 2020-07-24 at 13.44.59

time: O(n) space: the size of the tree, O(n)

Level Order Traversal (in one line)

Screen Shot 2020-07-24 at 13.53.38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class LevelOrderTraversal {

    public void levelOrder(Node root){

        if(root == null){
            System.out.println("Please enter a valid tree!");
            return;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);

        while(queue.size() > 0){
            root = queue.poll();
            System.out.print(root.data + " ");

            if(root.left != null){
                queue.add(root.left);
            }
            if(root.right != null){
                queue.add(root.right);
            }
        }
    }

    public static void main(String args[]){
        LevelOrderTraversal loi = new LevelOrderTraversal();
        BinaryTree bt = new BinaryTree();
        Node head = null;
        head = bt.addNode(10, head);
        head = bt.addNode(15, head);
        head = bt.addNode(5, head);
        head = bt.addNode(7, head);
        head = bt.addNode(19, head);
        head = bt.addNode(20, head);
        head = bt.addNode(-1, head);
        loi.levelOrder(head);
    }
}

Level by Level Printing (in different line)

  1. use 2 quesues

Screen Shot 2020-07-25 at 00.49.14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void levelByLevelTwoQueue(Node root) {
    if (root==null) return;
    Queue<Node> q1 = new Queue<Node>();
    Queue<Node> q2 = new Queue<Node>();
    q1.add(root);
    while ( !q1.isEmpty() || !q2.isEmpty() ) {
        while (!q1.isEmpty()) {
            root=q1.pull();
            System.out.print(root);
            if (root.left != null) {q2.add(root.left);}
            if (root.right != null) {q2.add(root.right);}
        }
        System.out.println();
        while (!q2.isEmpty()) {
            root=q2.pull();
            System.out.print(root);
            if (root.left != null) {q1.add(root.left);}
            if (root.right != null) {q1.add(root.right);}
        }
        System.out.println();
    }
}
  1. use 1 queue

Screen Shot 2020-07-25 at 00.52.36

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

void levelByLevelOneQueueUsingDelimiter(Node root) {
    if (root==null) return;
    Queue<Node> q = new Queue<Node>();
    q.add(root);
    while (!q.isEmpty()) {
        root=q.poll();
        if (root==null) {
            System.out.println();
            break
        }
        if (root != null) {
            System.out.print(root.data + " ");
            if (root.left != null) {
                q.add(root.left);
            }
            if (root.left != null) {
                q.add(root.left);
            }
        }
        q.add(null);
    }
}

public void levelByLevelOneQueueUsingDelimiter(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<Node>();
    q.offer(root);
    q.offer(null);
    while (!q.isEmpty()) {
        root = q.poll();
        if (root != null) {
            System.out.print(root.data + " ");
            if (root.left != null) {
                q.offer(root.left);
            }
            if (root.right != null) {
                q.offer(root.right);
            }
        } else {
            if (!q.isEmpty()) {
                System.out.println();
                q.offer(null);
            }
        }
    }
}
  1. 1 queue & 2 conter

Screen Shot 2020-07-25 at 01.41.49

Screen Shot 2020-07-25 at 00.57.11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public void levelByLevelOneQueueUsingCount(Node root) {
    if (root == null) return;

    Queue<Node> q = new LinkedList<Node>();
    int levelCount = 1;
    int currentCount = 0;
    int current = 0;

    q.add(root);

    while (!q.isEmpty()) {
        while (levelCount > 0) {
            current = q.poll();
            if (current.left != null) {
                q.add(root.left);
                currentCount++;
            }
            if (current.right != null) {
                q.add(root.right);
                currentCount++;
            }
            System.out.print(current.data + " ");
            levelCount--;
        }
        System.out.println();
        levelCount = currentCount;
        currentCount = 0;
    }

}

Reverse level order traversal binary tree

Screen Shot 2020-07-25 at 01.55.58

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public void reverseLevelOrderTraversal(Node root) {
    if (root=null) return;
    Stack<Node> s = new Stack<Node>();
    Queue<Node> q = new Queue<Node>();
    q.add(root);
    while(!q.isEmpty()){
        current = q.poll();
        if (current.right != null) {
            q.add(root.right);
        }
        if (current.left != null) {
            q.add(root.left);
        }
        s.push(current)
    }
    while(!s.isEmpty()){
        System.out.print(s.pop().data + " ");
    }
}

Handshaking Lemma and Interesting Tree Properties ??

Enumeration of Binary Trees ???

A Binary Tree is labeled if every node is assigned a label a Binary Tree is unlabeled if nodes are not assigned any label.

1
2
3
4
5
6
7
8
9

Below two are considered same unlabeled trees
    o                 o
  /   \             /   \
 o     o           o     o

Below two are considered different labeled trees
    A                C
  /   \             /  \
 B     C           A    B

How many different Unlabeled Binary Trees can be there with n nodes?

1
2
3
4
5
6
7
8
9
10
11
12
13
14

For n  = 1, there is only one tree
   o

For n  = 2, there are two possible trees
   o      o
  /        \
 o          o

For n  = 3, there are five possible trees
    o      o           o         o      o
   /        \         /  \      /         \
  o          o       o    o     o          o
 /            \                  \        /
o              o                  o      o

The idea is to consider all possible pair of counts for nodes in left and right subtrees and multiply the counts for a particular pair. Finally add results of all pairs.

1
2
3
4
5
6
7
8
9
10

For example, let T(n) be count for n nodes.
T(0) = 1  [There is only 1 empty tree]
T(1) = 1
T(2) = 2

T(3) =  T(0)*T(2) + T(1)*T(1) + T(2)*T(0) = 1*2 + 1*1 + 2*1 = 5

T(4) =  T(0)*T(3) + T(1)*T(2) + T(2)*T(1) + T(3)*T(0)
     =  1*5 + 1*2 + 2*1 + 5*1
     =  14

The above pattern basically represents n`th Catalan Numbers. First few catalan numbers are 1 1 2 5 14 42 132 429 1430 4862,… T(n)=\sum_{i=1}^{n}T(i-1)T(n-i)=\sum_{i=0}^{n-1}T(i)T(n-i-1)=C_n Here, T(i-1) represents number of nodes on the left-sub-tree T(n−i-1) represents number of nodes on the right-sub-tree

n`th Catalan Number can also be evaluated using direct formula.

T(n) = (2n)! / (n+1)!n! Number of Binary Search Trees (BST) with n nodes is also same as number of unlabeled trees. The reason for this is simple, in BST also we can make any key as root, If root is i`th key in sorted order, then i-1 keys can go on one side and (n-i) keys can go on other side.

How many labeled Binary Trees can be there with n nodes? To count labeled trees, we can use above count for unlabeled trees. The idea is simple, every unlabeled tree with n nodes can create n! different labeled trees by assigning different permutations of labels to all nodes.

Therefore,

Number of Labeled Tees = (Number of unlabeled trees) * n! = [(2n)! / (n+1)!n!] × n! For example for n = 3, there are 5 * 3! = 5*6 = 30 different labeled trees

Insertion in a Binary Tree

binary-tree-insertion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

import java.util.LinkedList;
import java.util.Queue;

public class GFG {

	/* A binary tree node has key, pointer to
	left child and a pointer to right child */
	static class Node {
		int key;
		Node left, right;

		// constructor
		Node(int key) {
			this.key = key;
			left = null;
			right = null;
		}
  }

	static Node root;
	static Node temp = root;

	/* Inorder traversal of a binary tree*/
	static void inorder(Node temp) {
		if (temp == null)
			return;
		inorder(temp.left);
		System.out.print(temp.key+" ");
		inorder(temp.right);
	}

	/*function to insert element in binary tree */
	static void insert(Node temp, int key) {
		Queue<Node> q = new LinkedList<Node>();
		q.add(temp);

		// Do level order traversal until we find
		// an empty place.
		while (!q.isEmpty()) {
			temp = q.peek();
			q.remove();

			if (temp.left == null) {
				temp.left = new Node(key);
				break;
			} else
				q.add(temp.left);

			if (temp.right == null) {
				temp.right = new Node(key);
				break;
			} else
				q.add(temp.right);
		}
	}

	// Driver code
	public static void main(String args[]) {
		root = new Node(10);
		root.left = new Node(11);
		root.left.left = new Node(7);
		root.right = new Node(9);
		root.right.left = new Node(15);
		root.right.right = new Node(8);

		System.out.print( "Inorder traversal before insertion:");
		inorder(root);

		int key = 12;
		insert(root, key);

		System.out.print("\nInorder traversal after insertion:");
		inorder(root);
	}
}

Deletion in a Binary Tree BFS vs DFS for Binary Tree Binary Tree (Array implementation) AVL with duplicate keys Applications of tree data structure Applications of Minimum Spanning Tree Problem Continuous Tree Foldable Binary Trees Expression Tree Evaluation of Expression Tree Symmetric Tree (Mirror Image of itself)

exersice

Parse Tree

Parse trees can be used to represent real-world constructions like sentences or mathematical expressions.

define four rules as follows:

  • If the current token is a '(', add a new node as the left child of the current node, and descend to the left child.
  • If the current token is in the list ['+','-','/','*'], set the root value of the current node to the operator represented by the current token.
  • Add a new node as the right child of the current node and descend to the right child.
  • If the current token is a number, set the root value of the current node to the number and return to the parent.
  • If the current token is a ')', go to the parent of the current node.

example: ['(', '3', '+', '(', '4', '*', '5' ,')',')']

buildExp8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from pythonds.basic import Stack
from pythonds.trees import BinaryTree

def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree

    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()

        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()

        elif i == ')':
            currentTree = pStack.pop()

        elif i not in ['+', '-', '*', '/', ')']:
            try:
                currentTree.setRootVal(int(i))
                parent = pStack.pop()
                currentTree = parent

            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))

    return eTree

pt = buildParseTree("( ( 10 + 5 ) * 3 )")
pt.postorder()  #defined and explained in the next section

import operator
def evaluate(parseTree):
    opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}

    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()

    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootVal()

Evaluating the expression represented by an expression tree:

Let t be the expression tree If t is not null then If t.value is operand then Return t.value A = solve(t.left) B = solve(t.right)

1
2
3

  // calculate applies operator 't.value'
  // on A and B, and returns value
  Return calculate(A, B, t.value)

Check Same Binary Tree

Screen Shot 2020-07-24 at 11.27.26 time O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class SameTree {

    public boolean sameTree(Node root1, Node root2){
        if(root1 == null && root2 == null){
            return true;
        }
        if(root1 == null || root2 == null){
            return false;
        }
        return root1.data == root2.data &&
                sameTree(root1.left, root2.left) &&
                sameTree(root1.right, root2.right);
    }

    public static void main(String args[]){
        BinaryTree bt = new BinaryTree();
        Node root1 = null;
        root1 = bt.addNode(10, root1);
        root1 = bt.addNode(20, root1);
        root1 = bt.addNode(15, root1);
        root1 = bt.addNode(2, root1);

        Node root2 = null;
        root2 = bt.addNode(10, root2);
        root2 = bt.addNode(20, root2);
        root2 = bt.addNode(15, root2);
        root2 = bt.addNode(2, root2);

        SameTree st = new SameTree();
        assert st.sameTree(root1, root2);
   }
}

.

00CodeNote, DS
This post is licensed under CC BY 4.0 by the author.

Comments powered by Disqus.