> For the complete documentation index, see [llms.txt](https://bryan-guner.gitbook.io/my-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bryan-guner.gitbook.io/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree.md).

# Tree

{% content-ref url="/pages/Tn4e1ebm848TGGO6Vvdo" %}
[In Order Traversal](/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/in-order-traversal.md)
{% endcontent-ref %}

{% content-ref url="/pages/0nBLsepeIEptcDRH3xst" %}
[Tree Equal ?](/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/tree-equal.md)
{% endcontent-ref %}

{% content-ref url="/pages/9QqqjG9WE8GqeMszGlrn" %}
[Ternary-search-trees](/my-docs/pythonnotes/abstract-data-structures/untitled-1/tree/ternary-search-trees.md)
{% endcontent-ref %}

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

{% content-ref url="/pages/OrQuGTtIccjIeMPJAbNv" %}
[Tree Traversals (Inorder, Preorder and Postorder)](/my-docs/pythonnotes/curriculum/untitled-4/untitled-5/tree-traversals-inorder-preorder-and-postorder.md)
{% endcontent-ref %}

{% content-ref url="/pages/4MLckUBho4k21aTeMpO8" %}
[Set](/my-docs/pythonnotes/abstract-data-structures/untitled-1/set.md)
{% endcontent-ref %}

{% content-ref url="/pages/K2Fb2qoBZc5fio9pP5ZI" %}
[Binary Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/WvqmSzLeimHHeTzSVLwo" %}
[Binary Search Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/K2Fb2qoBZc5fio9pP5ZI" %}
[Binary Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree.md)
{% 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="/pages/enW2lSXXp3eJnMVAPOII" %}
[Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array.md)
{% endcontent-ref %}

{% content-ref url="/pages/WvqmSzLeimHHeTzSVLwo" %}
[Binary Search Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-search-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/elNgqdtjORrnmaofkEgI" %}
[Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4.md)
{% endcontent-ref %}

{% content-ref url="/pages/vgEVzHJattVXgB9JCcXO" %}
[Extra-Array](/my-docs/pythonnotes/abstract-data-structures/untitled-1/array/extra-array.md)
{% endcontent-ref %}

{% content-ref url="/pages/7eiX2YnAhvNnjY7OiRJy" %}
[Stack](/my-docs/pythonnotes/abstract-data-structures/untitled-1/stack.md)
{% endcontent-ref %}

{% content-ref url="/pages/K2Fb2qoBZc5fio9pP5ZI" %}
[Binary Tree](/my-docs/pythonnotes/abstract-data-structures/untitled-1/binary-tree.md)
{% endcontent-ref %}

{% content-ref url="/pages/5w44kr7eSNwzBPsybKTo" %}
[Recursion](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-6.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/BLnvGjl0WoqZ9npdIr6P" %}
[Searching](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-2.md)
{% endcontent-ref %}

{% content-ref url="/pages/aDu8lYDCInQiGtYNEfzQ" %}
[Sorting](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-3.md)
{% endcontent-ref %}

{% content-ref url="/pages/nemaGQmas79yIx2pLK7y" %}
[Queue Sandbox](/my-docs/pythonnotes/abstract-data-structures/untitled-1/queue/queue-sandbox.md)
{% endcontent-ref %}

{% content-ref url="/pages/4w3lLbf7UKIMgQ0GuYjN" %}
[Hash Table](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-5.md)
{% endcontent-ref %}

{% content-ref url="/pages/Bw6QkD4iYM6zszBi6Pvs" %}
[Double Linked List](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-4/double-linked-list.md)
{% endcontent-ref %}

{% content-ref url="/pages/WKSCy91DvXLWkyMYSwoP" %}
[Graphs](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled-1.md)
{% endcontent-ref %}

{% content-ref url="/pages/HA6U4P21mzp0ei2zS5qt" %}
[Exotic](/my-docs/pythonnotes/abstract-data-structures/untitled-1/untitled.md)
{% endcontent-ref %}

{% content-ref url="/pages/bS4bA0QClN1EyxgFa7pw" %}
[Heap](/my-docs/pythonnotes/abstract-data-structures/untitled-1/heap.md)
{% endcontent-ref %}