# Tree

{% content-ref url="tree/in-order-traversal" %}
[in-order-traversal](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/in-order-traversal)
{% endcontent-ref %}

{% content-ref url="tree/tree-equal" %}
[tree-equal](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/tree-equal)
{% endcontent-ref %}

{% content-ref url="tree/ternary-search-trees" %}
[ternary-search-trees](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/ternary-search-trees)
{% endcontent-ref %}

{% content-ref url="red:black-tree.md" %}
<red:black-tree.md>
{% endcontent-ref %}

{% content-ref url="../../curriculum/untitled-4/untitled-5/tree-traversals-inorder-preorder-and-postorder" %}
[tree-traversals-inorder-preorder-and-postorder](https://bryan-guner.gitbook.io/my-docs/pythonnotes/curriculum/untitled-4/untitled-5/tree-traversals-inorder-preorder-and-postorder)
{% endcontent-ref %}

{% content-ref url="set" %}
[set](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/set)
{% endcontent-ref %}

{% content-ref url="binary-tree" %}
[binary-tree](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree)
{% endcontent-ref %}

{% content-ref url="binary-search-tree" %}
[binary-search-tree](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree)
{% endcontent-ref %}

{% content-ref url="binary-tree" %}
[binary-tree](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree)
{% endcontent-ref %}

### Trees in Python

[Trees](https://www.educative.io/blog/data-structures-trees-java) are another relation-based data structure, which specialize in representing hierarchical structures. Like a linked list, they’re populated with `Node` objects that contain a data value and one or more pointers to define its relation to immediate nodes.

Each tree has a **root** node that all other nodes branch off from. The root contains pointers to all elements directly below it, which are known as its **child nodes**. These child nodes can then have child nodes of their own. Binary trees cannot have nodes with more than two child nodes.

Any nodes on the same level are called **sibling nodes**. Nodes with no connected child nodes are known as **leaf nodes**.![](data:image/svg+xml;base64,PHN2ZyB3aWR0aD0iODE4NSIgaGVpZ2h0PSI2NTgwIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciIHZlcnNpb249IjEuMSIvPg==)![widget](https://www.educative.io/cdn-cgi/image/f=auto,fit=contain,w=600/api/page/4827483893923840/image/download/6470804819148800)![widget](https://www.educative.io/cdn-cgi/image/f=auto,fit=contain,w=300,q=10/api/page/4827483893923840/image/download/6470804819148800)

The most common application of the binary tree is a **binary search tree**. Binary search trees excel at searching large collections of data, as the time complexity depends on the depth of the tree rather than the number of nodes.

> **Binary search trees have four strict rules:**
>
> * The left subtree contains only nodes with elements lesser than the root.
> * The right subtree contains only nodes with elements greater than the root.
> * Left and right subtrees must also be a binary search tree. They must follow the above rules with the “root” of their tree.
> * There can be no duplicate nodes, i.e. no two nodes can have the same value.

{% content-ref url="array" %}
[array](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/array)
{% endcontent-ref %}

{% content-ref url="binary-search-tree" %}
[binary-search-tree](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree)
{% endcontent-ref %}

{% content-ref url="untitled-4" %}
[untitled-4](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4)
{% endcontent-ref %}

{% content-ref url="array/extra-array" %}
[extra-array](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/array/extra-array)
{% endcontent-ref %}

{% content-ref url="stack" %}
[stack](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/stack)
{% endcontent-ref %}

{% content-ref url="binary-tree" %}
[binary-tree](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree)
{% endcontent-ref %}

{% content-ref url="untitled-6" %}
[untitled-6](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-6)
{% endcontent-ref %}

{% content-ref url="untitled-5" %}
[untitled-5](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5)
{% endcontent-ref %}

{% content-ref url="untitled-2" %}
[untitled-2](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-2)
{% endcontent-ref %}

{% content-ref url="untitled-3" %}
[untitled-3](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-3)
{% endcontent-ref %}

{% content-ref url="queue/queue-sandbox" %}
[queue-sandbox](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/queue/queue-sandbox)
{% endcontent-ref %}

{% content-ref url="untitled-5" %}
[untitled-5](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5)
{% endcontent-ref %}

{% content-ref url="untitled-4/double-linked-list" %}
[double-linked-list](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4/double-linked-list)
{% endcontent-ref %}

{% content-ref url="untitled-1" %}
[untitled-1](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-1)
{% endcontent-ref %}

{% content-ref url="untitled" %}
[untitled](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled)
{% endcontent-ref %}

{% content-ref url="heap" %}
[heap](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/heap)
{% endcontent-ref %}